A Faster Algorithm for Linear Programming and the Maximum Flow Problem II

on YouTube ↗01h 01m

" summary

Claims a linear‑program interior‑point scheme that keeps Renegar‑style cheap iterations while matching the near‑optimal central‑path convergence (roughly √n iterations), implemented by a weighted log barrier derived from a regularized John ellipse, JL sketches to approximate leverage scores, and a “path‑finding” update that jointly nudges primal variables and constraint weights. Each iteration solves a polylog linear systems per iteration of Laplacian/DA form, giving maximum‑flow and min‑cost‑flow runtimes about m·√n (and matching previous sparse‑graph bounds up to polylog factors).

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:41Linear Programming
3. 2:39Standard Methods
4. 3:18Interior Point Methods
5. 3:55Previous Work
6. 9:43The Maximum Flow Problem
7. 20:06Renegar's Algorithm
8. 22:37Regularized John Ellipse Barrier
9. 23:49Should we hope for cheaper iterations?
10. 30:57Back to the Log Barrier
11. 41:29What? Free lunch? What about gradient?
12. 46:21Finding the Path
13. 47:39Recap
14. 54:00Running Time #2
15. 58:53Open Questions / Further Work