Solution Size Growth as an Obstacle to Iterative Refinement for Linear Optimization
Source: arxiv.org/abs/2611.11419
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…
Comments and reviews
No comments yet.
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}'