Delphi.science

Solution Size Growth as an Obstacle to Iterative Refinement for Linear Optimization

Source: arxiv.org/abs/2611.11419

Henry Graven, Giacomo Nannicini

arXivarxiv/2611.11419Nov 8, 2026math.OCscore 0

Iterative refinement is a technique used to exponentially boost the precision of the solution to certain problems by solving a sequence of related problem instances. We study the size of the solutions arising from the sequence of problems produced by the iterative refinement algorithm when applied to linear optimization problems (LPs). We introduce a class of problems for which the size of such solutions can grow exponentially with the number of refinement iterations, and we show evidence that to avoid this undesirable behavior, a black-box LP solver would have to be \emph{lucky}---a concept…

JSONText

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