Extended Formulations 1

on YouTube ↗58m

" summary

Quick tutorial that proves the core claims: extended formulations let some polytopes shrink from exponentially many inequalities to n×B network flow LP for knapsack by encoding the DP, and extension complexity equals nonnegative rank equals extension complexity via Yannakakis. Tools are explicit constructions, slack matrices, nonnegative factorizations and communication complexity (randomized protocols and rectangle covering number) to get exponential lower bounds (e.g., correlation polytope) and to connect to NP-hardness; open problem: FPTAS-size LPs remain unresolved.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:22Extended formulation
3. 3:12Motivation
4. 7:59A dynamic program for KNAPSACK
5. 9:16Knapsack (3)
6. 13:34Knapsack (4)
7. 17:05Knapsack (5)
8. 21:30Slack-matrix
9. 22:53Yannakakis Theorem
10. 29:21Rectangle covering lower bound
11. 34:13Communication complexity (3)
12. 40:16An exact model (1)
13. 49:59Correlation polytope (1)