Solving Linear Programs with Sqrt(rank) Linear System Solves

Abstract

We present an algorithm that given a linear program with $n$ variables, $m$ constraints, and constraint matrix $A$, computes an $\epsilon$-approximate solution in $\tilde{O}(\sqrt{rank(A)}\log (1/\epsilon ))$ iterations with high probability. Each iteration of our method consists of solving $\tilde{O}(1)$ linear systems and additional nearly linear time computation, improving by a factor of $\tilde{\Omega }((m/rank(A){)}^{1/2})$ over the previous fastest method with this iteration cost due to Renegar (1988). Further, we provide a deterministic polynomial time computable $\tilde{O}(rank(A))$-self-concordant barrier function for the polytope, resolving an open question of Nesterov and Nemirovski (1994) on the theory of "universal barriers" for interior point methods. Applying our techniques to the linear program formulation of maximum flow yields an $\tilde{O}(|E|\sqrt{|V|}\log (U))$ time algorithm for solving the maximum flow problem on directed graphs with $|E|$ edges, $|V|$ vertices, and integer capacities of size at most $U$. This improves upon the previous fastest polynomial running time of $O(|E|\min \{|E{|}^{1/2},|V{|}^{2/3}\}\log (|V{|}^2/|E|)\log (U))$ achieved by Goldberg and Rao (1998). In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of $O(|E|\min \{|E{|}^{1/2},|V{|}^{2/3}\})$ achieved by Even and Tarjan (1975) and Karzanov (1973) and of $\tilde{O}(|E{|}^{10/7})$ achieved more recently by Mądry (2013).

arXiv commentThe merged version of abs/1312.6677 and abs/1312.6713. It contains several new results beyond these prior submissions, including a nearly optimal self-concordant barrier and its relation to Lewis weight

References in corpus (8)

• Approaching optimality for solving SDD systems
• Sparsified Cholesky Solvers for SDD linear systems
• Solving Linear Programs in the Current Matrix Multiplication Time
• Conditional Hardness of Earth Mover Distance
• Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier
• Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves
• Iterative Row Sampling
• Universal Barrier is $n$-Self-Concordant

Cited by in corpus (11)

• Single-Sample Prophet Inequalities via Greedy-Ordered Selection
• Faster Divergence Maximization for Faster Maximum Flow
• Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
• Noticeability Versus Impact in Traffic Signal Tampering
• Interior-point methods on manifolds: theory and applications
• On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming
• Speeding up Linear Programming using Randomized Linear Algebra
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• The tropicalization of the entropic barrier
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
• Hardness of Graph-Structured Algebraic and Symbolic Problems