3 papers
math.OC2026
Circuit Diameter of Polyhedra is Strongly Polynomial
Bento Natura
We prove a strongly polynomial bound on the circuit diameter of polyhedra, resolving the circuit analogue of the polynomial Hirsch conjecture. Specifically, we show that the circui…
math.OC2025
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho +2
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an -variable linear program in standard form, the iteration…
math.OC2024
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015) as a relaxation of the combinatorial diameter. We show that the circuit diam…