{"id":"arxiv/2608.08861","url":"https://arxiv.org/abs/2608.08861","tags":["math.OC"],"score":0,"title":"Simultaneous Group-Envelope Bounds for $Γ$-Robust Multiple-Choice Knapsack Problems","domain":"math.OC","source":"arxiv","authors":["Zi Yuan Eric Shao"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}