Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems
Many robust planning problems are solved by checking a family of ordinary optimization problems, one for each uncertainty threshold. Repeatedly building and solving those relaxations can dominate runtime. We show that, when a decision chooses exactly one option from each group, the entire threshold family of multiple-choice knapsack relaxations can instead be bounded together. A cancellation removes threshold-specific baselines and reduces each group's contribution to two simple envelopes. After sorting, one multiplier is evaluated across all thresholds in time linear in their number and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.08861
curl -X POST /api/v1/records/arxiv/2608.08861/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.08861/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'