Solving linear programs in the current matrix multiplication time

DOI10.1145/3313276.3316303zbMath1437.90097arXiv1810.07896OpenAlexW2962921664MaRDI QIDQ5212834

Yin Tat Lee, Michael B. Cohen, 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

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

Related Items (11)

Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ Tensors in computations ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Linear equations for unordered data vectors in $[D^k\to{}Z^d$] ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ A faster interior-point method for sum-of-squares optimization ⋮ Bayesian persuasion: reduced form approach ⋮ Unnamed Item ⋮ Greedy rectilinear drawings ⋮ Limits on the Universal method for matrix multiplication ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

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