Delphi.science

Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time

Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, László A. Végh

arXivarxiv/2610.26073Oct 19, 2026math.OCscore 0

Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.26073
curl -X POST /api/v1/records/arxiv/2610.26073/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26073/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'