Constructing Extended Formulations

on YouTube ↗01h 07m

" summary

Six constructive recipes and concrete bounds: disjunctive programming yields convex-union formulations (used to get log‑n matching polytopes via perfect‑hash families of size 2^{O(k)} log n); a parity polytope drops 2^{N-1} facets to a 4N−4 arc flow extension; dynamic programming translates DP shortest‑path DAGs to extensions (log‑n cycle polytope becomes polynomial‑size); branched polyhedral systems unify the two; dualization links spanning‑tree and nonempty‑subgraph polytopes; adding redundant information (primal/dual arborescences) gives linear‑size planar spanning‑tree formulations and practical speedups.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 4:35Convex Hulls and Linear Programming
3. 7:06Representations as Projections
4. 12:37Completion Times Polytope
5. 16:13Unions of Polytopes
6. 19:03Special Matchings
7. 20:19Colorful Matching Polytopes
8. 21:35Making all Matchings Colorful
9. 22:31Perfect Hash Functions
10. 25:19Outline
11. 26:04Special Cycles
12. 28:38Colorful Cycles with Prescribed Node a
13. 30:29Colorful Cycle Polytopes (Prescribed Node)
14. 30:58Combining Things for Cycle Polytopes
15. 33:26Hyperpath Polytopes
16. 35:21Branched Combinatorial/Polyhedral Systems
17. 38:56Extended Formulatations via Duality
18. 42:10Application to Spanning Tree Polytopes
19. 46:02Extended Formulations for Non-Empty Subgraphs Polytopes All Subgraphs Polytope of G
20. 48:02Non-Extended Formulations of Nonempty-Subgraphs Polytopes
21. 48:53Graphs of Bounded Genus
22. 52:04Spanning Trees in Planar Graphs
23. 53:51Linear Description of Pub
24. 58:09Polynomial Spanning Tree Optimization Setup for G=(V. E), MS2 (acyclic subsets)