Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow

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.

Authors

• Yin Tat Lee
• Aaron Sidford

Keywords

• Linear systems
• Standards
• Linear programming
• Convergence
• Approximation methods
• Polynomials
• Laplace equations
• Pathfinding
• Maximum Flow
• Running Time
• Linear System
• Directed Graph
• Flow Problem
• Capacity Ratio
• Flow Algorithm
• Linear Programming Formulation
• Barrier Function
• Convergence Rate
• Undirected
• Weight Function
• Linear Solver
• Newton Method
• Convex Optimization Problem
• Convex Set
• Interior Point
• Current Point
• Interior Point Method
• Standardized Path
• Central Path
• Minimum Cost Flow
• Linear Programming Algorithm
• Polytope
• Gradient Descent Method
• Sparse Graph
• Universal Function
• Feasible Point
• linear program