Solving Linear Programs with Sqrt(rank) Linear System Solves

MaRDI QIDQ6327401arXivFDO

Authors Yin Tat Lee, Aaron Sidford

Publication date 17 October 2019

Published in arXiv

arXiv classification

cs.DSmath.OC

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 $ildeO(sqrtrank(A)log(1/epsilon))$ iterations with high probability. Each iteration of our method consists of solving $ildeO(1)$ linear systems and additional nearly linear time computation, improving by a factor of $ildeOmega((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 $ildeO(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 $ildeO(|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 $ildeO(|E{|}^{10/7})$ achieved more recently by Mk{a}dry (2013).

Cited in

(1)

• Computing Lewis Weights to High Precision by Fixed-Point Iteration

This page was built for publication: Solving Linear Programs with Sqrt(rank) Linear System Solves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6327401)