Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

on YouTube ↗53m

" summary

Replaces the standard Min-Inner-Product shortest-path oracle with a packing Min-IP oracle that returns a maximally-disjoint set of short paths (like blocking flows) and proves the multiplicative-weights iteration count drops from Θ(m) to ~Θ(√m), which is optimal. Shows the packing oracle can sometimes be implemented no harder than the single-path oracle (e.g. via max-flow plus DFS to extract cuts/paths), and outlines how faster packing than decremental Min-IP could beat the O(mn) barrier for LPs such as Min Steiner Cut (current ε dependence ≈1/ε^3).

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 2:03Network Design via Packing LPs
3. 10:18PD-MWU Framework for apx Packing LPs [Garg-Konemann'98]
4. 37:11Reducing MwU Iterations via Min-Row-Packing [KWY 23]
5. 43:34Proof of MSP Theorem
6. 47:18Accelerating Network Design LPs via the MSP Oracle