Solving linear programs in the current matrix multiplication time

DOI10.1145/3313276.3316303MaRDI QIDQ5212834zbMATH OpenOpenAlexFDO

Authors Michael B. Cohen, Yin Tat Lee, Zhao Song

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07896

zbMATH Keywords

interior point methodlinear programmatrix multiplication

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Linear programming (90C05) Interior-point methods (90C51)

Abstract: This paper shows how to solve linear programs of the form $mi{n}_{Ax=b,xgeq0}{c}^{o}px$ with $n$ variables in time ${\displaystyle }$O^*((n^{omega}+n^{2.5-alpha/2}+n^{2+1/6}) log(n/delta))${\displaystyle }$ where $omega$ is the exponent of matrix multiplication, $alpha$ is the dual exponent of matrix multiplication, and $delta$ is the relative accuracy. For the current value of $omegasim2.37$ and $alphasim0.31$, our algorithm takes $O^{\ast }(n^{omega}log(n/delta))$ time. When $omega=2$, our algorithm takes $O^{\ast }(n^{2+1/6}log(n/delta))$ 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 $sqrtW{A}^{op}(AW{A}^{op}{)}^{-1}AsqrtW$ in sub-quadratic time under $el{l}_2$ multiplicative changes in the diagonal matrix $W$.

Recommendations

• Solving Linear Programs in the Current Matrix Multiplication Time
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Linear Programming in O([n3/ln n]L) Operations
• Nearly-linear time positive LP solver with faster convergence rate
• A new polynomial-time algorithm for linear programming

Cited in

(23)

• Solving related two- and three-dimensional linear programming problems in logarithmic time
• Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Nearly-linear time positive LP solver with faster convergence rate
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Solving Linear Programs in the Current Matrix Multiplication Time
• Linear equations for unordered data vectors in $[D]^k\to{}Z^d$
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• scientific article; zbMATH DE number 7559394 (Why is no real title available?)
• Limits on the Universal method for matrix multiplication
• Solving tall dense linear programs in nearly linear time
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Tensors in computations
• Greedy rectilinear drawings
• A faster interior-point method for sum-of-squares optimization
• Bayesian persuasion: reduced form approach
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• High-accuracy multicommodity flows via iterative refinement
• Interior point methods are not worse than simplex
• Negative-weight single-source shortest paths in near-linear time
• Barriers for rectangular matrix multiplication
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• The complexity of envy-free graph cutting

This page was built for publication: Solving linear programs in the current matrix multiplication time

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