# Solving Linear Programs in the Current Matrix Multiplication Time

Preprint · Michael B. Cohen, Yin Tat Lee, Zhao Song

- Archive id: arxiv:1810.07896
- Published: 2018-10-18
- arXiv: https://arxiv.org/abs/1810.07896
- Source URL: https://arxiv.org/abs/1810.07896
- PDF: https://arxiv.org/pdf/1810.07896
- Provenance: arxiv

## Abstract

This paper shows how to solve linear programs of the form $\\min\_{Ax=b,x\\geq0} c^\\top x$ with $n$ variables in time $$O^\*((n^ω+n^{2.5-α/2}+n^{2+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 $ω\\sim2.37$ and $α\\sim0.31$, our algorithm takes $O^\*(n^ω \\log(n/δ))$ time. When $ω= 2$, our algorithm takes $O^\*(n^{2+1/6} \\log(n/δ))$ time. Our algorithm utilizes several new concepts that we believe may be of independent interest: $\\bullet$ We define a stochastic central path method. $\\bullet$ We show how to maintain a projection matrix $\\sqrt{W}A^{\\top}(AWA^{\\top})^{-1}A\\sqrt{W}$ in sub-quadratic time under $\\ell\_{2}$ multiplicative changes in the diagonal matrix $W$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.