A Faster Algorithm for Linear Programming and the Maximum Flow Problem I
summary
Presents a new interior‑point framework that replaces the log barrier with a regularized volumetric (joint‑ellipsoid) barrier computable via Lewis weights / Lp Lewis weights, proving the method needs about sqrt(n) iterations (more precisely O~(sqrt{λ}) with λ≈n for the final barrier) instead of the log‑barrier’s √m; recovers Vaidya’s MN1/4 bound via one step of the process, implements a smoothed fixed‑point for the weight vector, and flags remaining engineering issues for m‑variable Max‑Flow and fast leverage computations.
AI-written summary · about
chapters (17)
- 0:00Introduction to LP problem
- 0:35Iterative methods background
- 1:49Previous research progress
- 4:30Framework of center-based LP
- 6:22The role of barrier functions
- 9:01Self-concordance and geometry
- 10:35Algorithm steps and logic
- 12:04Convergence and complexity
- 17:08Analyzing duality gaps
- 18:36Primal-dual potential functions
- 20:03Limitations of standard barriers
- 22:40Leverage scores and geometry
- 25:21Volumetric barrier introduction
- 27:03Weighting and regularization
- 34:52John ellipsoids and limits
- 36:38Recursive barrier refinement
- 40:01Conclusion and future work