Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow
Authors:
- Yin Tat LeeYLYin Tat Lee
- Aaron SidfordASAaron Sidford
Top Cited Papers
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 424-433
Abstract
In this paper, we present a new algorithm for '/ solving linear programs that requires only Õ(√rank(A)L) iterations where A is the constraint matrix of a linear program with m constraints, n variables, and bit complexity L. Each iteration of our method consists of solving Õ(1) linear systems and additional nearly linear time computation. Our method improves upon the previous best iteration bounds by factor Ω̃((m/rank (A))) 1/4 ) of for methods with polynomial time computable iterations and by Ω̃((m/rank (A)) 1/2 ) for methods which solve at most Õ(1) linear systems in each iteration each achieved over 20 years ago. Applying our techniques to the linear program formulation of maximum flow yields an Õ(|E| √|V| log 2 U) time algorithm for solving the maximum flow problem on directed graphs with |E| edges, |V| vertices, and capacity ratio U. This improves upon the previous fastest running time of O(|E| min{|E| 1/2 , |V| 2/3 } log (|V| 2 /|E|) log(U)) achieved over 15 years ago by Goldberg and Rao and improves upon the previous best running times for solving dense directed unit capacity graphs of Õ(|E| min{|E| 1/2 , |V| 2/3 }) achieved by Even and Tarjan over 35 years ago and a running time of Õ(|E| 10/7 ) achieved recently by Madry.Keywords
This publication has 34 references indexed in Scilit:
- Rounding of convex sets and efficient gradient methods for linear programming problemsOptimization Methods and Software, 2008
- Simulated annealing in convex bodies and an volume algorithmJournal of Computer and System Sciences, 2006
- Beyond the flow decomposition barrierJournal of the ACM, 1998
- A new algorithm for minimizing convex functions over convex setsMathematical Programming, 1996
- Path-Following Methods for Linear ProgrammingSIAM Review, 1992
- An O (n 2 (m + N log n )log n ) min-cost flow algorithmJournal of the ACM, 1988
- A polynomial-time algorithm, based on Newton's method, for linear programmingMathematical Programming, 1988
- A strongly polynomial minimum cost circulation algorithmCombinatorica, 1985
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972