Faster Linear Programming with √(rank) Linear System Solves
Abstract
Lee and Sidford [LS19] showed that the linear program min{c⊤ x : A⊤ x=b, l≤ x≤ u} over x∈ℝm, where A∈ℝm× n, can be solved to accuracy ε using O(√nlog13m·log(mU/ε)) solves of linear systems in A⊤DA for positive diagonal matrices D, where U bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by rank(A)=n rather than by the number of constraints m. Song [Son19] mentioned that reducing the log13m factor is an interesting future direction. Given an interior point and a finite certified magnitude bound U, we give an algorithm that uses O(√nlog4m·log(mU/ε)) solves of such linear systems, improving the Lee--Sidford bound by a factor of log9m. We conjecture that O(√nlog(mU/ε)) such linear-system solves suffice.
Related
- Faster quantum linear system solver beyond the condition number
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- PDLP: a practical first-order method for large-scale linear programming
- Newton Steps are Faster for Linear Complementarity Problems
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
BibTeX
@misc{song2026faster,
title = {{Faster Linear Programming with $\sqrt\mathrmrank$ Linear System Solves}},
author = {Zhao Song},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30853},
eprint = {2609.30853},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30853},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Faster Linear Programming with √(rank) Linear System Solves
AU - Zhao Song
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30853
UR - https://arxiv.org/abs/2609.30853
AB - Lee and Sidford [LS19] showed that the linear program min{c^⊤ x : A^⊤ x=b, l≤ x≤ u} over x∈ℝ^m, where A∈ℝ^m× n, can be solved to accuracy ε using O(√nlog^13m·log(mU/ε)) solves of linear systems in A^⊤DA for positive diagonal matrices D, where U bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by rank(A)=n rather than by the number of constraints m. Song [Son19] mentioned that reducing the log^13m factor is an interesting future direction. Given an interior point and a finite certified magnitude bound U, we give an algorithm that uses O(√nlog^4m·log(mU/ε)) solves of such linear systems, improving the Lee--Sidford bound by a factor of log^9m. We conjecture that O(√nlog(mU/ε)) such linear-system solves suffice.
ER -