A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

DOI10.1145/3357713.3384326OpenAlexW3035139670MaRDI QIDQ5144961

Sophie Huiberts, Daniel Dadush, Bento Natura, László A. Végh

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingcondition numbercircuitsinterior point methodslinear matroidschi bar

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

On circuit diameter bounds via circuit imbalances ⋮ An update-and-stabilize framework for the minimum-norm-point problem ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

This page was built for publication: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix