{"id":"arxiv/2602.05699","url":"https://arxiv.org/abs/2602.05699","tags":["math.OC"],"score":0,"title":"On Circuit Diameter and Straight Line Complexity","domain":"math.OC","source":"arxiv","authors":["Daniel Dadush","Stefan Kober","Zhuan Khye Koh"],"reviews":0,"subject":"math.OC","summary":"The circuit diameter of a polyhedron is the maximum length (number of steps) of a shortest circuit walk between any two vertices of the polyhedron. Introduced by Borgwardt, Finhold and Hemmecke (SIDMA 2015), it is a relaxation of the combinatorial diameter of a polyhedron. These two notions of diameter lower bound the number of iterations taken by circuit augmentation algorithms and the simplex method respectively for solving linear programs. Recently, an analogous lower bound for path-following interior point methods was introduced by Allamigeon, Dadush, Loho, Natura and Végh (SICOMP 2025).…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-05","reactions":{}}