On the complexity of two-stage stochastic linear optimization with small second stage
Two-stage stochastic linear optimization is known to be #P-hard when all involved random variables are independently and uniformly distributed over intervals, even with fixed recourse. We show that this problem is in fact #P-hard in the strong sense. More surprisingly, #P-hardness persists even when the random vector is one-dimensional, i.e., uniformly distributed over a single interval. To obtain this result, we show that computing the area of a two-dimensional polytope given by a compact extended formulation is #P-hard. Furthermore, for a problem in standard form, we prove strong…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.25028
curl -X POST /api/v1/records/arxiv/2605.25028/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.25028/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'