Solving Linear Programs in the Current Matrix Multiplication Time
Open Access
- 5 January 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (1), 1-39
- https://doi.org/10.1145/3424305
Abstract
This article shows how to solve linear programs of the form minAx=b,x≥ 0 c⊤ x with n variables in time O*((nω+n2.5−α/2+n2+1/6) log (n/δ)), where ω is the exponent of matrix multiplication, α is the dual exponent of matrix multiplication, and δ is the relative accuracy. For the current value of ω δ 2.37 and α δ 0.31, our algorithm takes O*(nω log (n/δ)) time. When ω = 2, our algorithm takes O*(n2+1/6 log (n/δ)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: • We define a stochastic central path method. • We show how to maintain a projection matrix √ WA⊤ (AWA⊤)−1A√ W in sub-quadratic time under \ell2 multiplicative changes in the diagonal matrix W.Keywords
Funding Information
- Amazon
- NSF (CCF-1740551, CCF-1749609, and DMS-1839116)
- Schmidt Foundation
- Ma Huateng Foundation
- DARPA/SRC
- Simons Foundation
This publication has 42 references indexed in Scilit:
- Fast Matrix MultiplicationPublished by Association for Computing Machinery (ACM) ,2015
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication ConjecturePublished by Association for Computing Machinery (ACM) ,2015
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear timePublished by Association for Computing Machinery (ACM) ,2013
- Improved bound for complexity of matrix multiplicationProceedings of the Royal Society of Edinburgh: Section A Mathematics, 2013
- Multiplying matrices faster than coppersmith-winogradPublished by Association for Computing Machinery (ACM) ,2012
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Self-regular functions and new search directions for linear and semidefinite optimizationMathematical Programming, 2002
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming AlgorithmMathematics of Operations Research, 1994
- Acceleration and Parallelization of the Path-Following Interior Point Method for a Linearly Constrained Convex Quadratic ProblemSIAM Journal on Optimization, 1991
- A new polynomial-time algorithm for linear programmingPublished by Association for Computing Machinery (ACM) ,1984