On Circuit Diameter and Straight Line Complexity
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).…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.05699
curl -X POST /api/v1/records/arxiv/2602.05699/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.05699/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'