Faster High Accuracy Multi-Commodity Flows via Graph Techniques

on YouTube ↗45m

" summary

Graph techniques give a concrète speedup for high‑accuracy multi‑commodity flow by reducing the problem to a dynamic HeavyHitter data structure on incidence matrices and solving that with an expander decomposition plus the central path reduction. The result replaces prior LP‑solver bounds (≈m^ω) with roughly √m · n^{ω−1/2} for dense k‑commodity instances, proves a constant (≈6×) near‑orthogonality bound for the k‑block split, and produces a working dynamic routine with delete/query guarantees; extending this to general sparse LPs remains open.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:32Problem definitions
3. 2:21High accuracy regime
4. 3:19Linear programs as flow
5. 5:00History and graph techniques
6. 8:01Hardness reduction
7. 10:38Graph-based improvements
8. 13:21Heavy hitter problem
9. 17:03Sparse matrix challenge
10. 20:53Incidence matrix reduction
11. 25:55Orthogonal decomposition
12. 33:24Future work and questions
13. 36:40Expander decomposition