Solving Linear Programs in the Current Matrix Multiplication Time

2018/10/18 by Michael B. Cohen, Yin Tat Lee, Cohen, Michael B. +3 · 13 citations
Computer Science · #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1810.07896

Abstract

This paper shows how to solve linear programs of the form min_Ax=b,x≥0 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 ω∼2.37 and α∼0.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 √(W)A^\top(AWA^\top)^-1A√(W) in sub-quadratic time under ℓ₂ multiplicative changes in the diagonal matrix W.

Cited by

• Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy
• Quantum Interior Point Methods: A Review of Developments and An Optimally Scaling Framework
• Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints
• Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
• Decentralized Detection with Robust Information Privacy Protection
• Adaptive Sparsification for Linear Programming
• Towards Sampling Data Structures for Tensor Products in Turnstile Streams
• Large Language Model-Empowered Decision Transformer for UAV-Enabled Data Collection
• Minimizing Convex Functions with Rational Minimizers
• Doubly-Efficient Pseudo-Deterministic Proofs
• Reusing Samples in Variance Reduction
• A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• Tesserae: Scalable Placement Policies for Deep Learning Workloads
• Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes

Related

• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
• A new quadratic-time number-theoretic algorithm to solve matrix multiplication problem
• An O(n²log⁴ n log log n) Time Matrix Multiplication Algorithm