A note on the complexity of two-stage stochastic linear optimization with small second stage
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917529154224128 |
|---|---|
| author | Buchheim, Christoph |
| author_facet | Buchheim, Christoph |
| contents | 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 actually #P-hard in the strong sense. More surprisingly, this hardness persists 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 strongly #P-hard. Furthermore, we obtain the same complexity result in case the number of second-stage constraints is fixed (for a problem in standard form), while fixing the number of second-stage variables leads to a weakly #P-hard problem. Finally, if both the dimension of the random vector and the number of second-stage constraints are fixed, the problem turns out to be tractable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25028 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on the complexity of two-stage stochastic linear optimization with small second stage Buchheim, Christoph Optimization and Control 90C15 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 actually #P-hard in the strong sense. More surprisingly, this hardness persists 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 strongly #P-hard. Furthermore, we obtain the same complexity result in case the number of second-stage constraints is fixed (for a problem in standard form), while fixing the number of second-stage variables leads to a weakly #P-hard problem. Finally, if both the dimension of the random vector and the number of second-stage constraints are fixed, the problem turns out to be tractable. |
| title | A note on the complexity of two-stage stochastic linear optimization with small second stage |
| topic | Optimization and Control 90C15 |
| url | https://arxiv.org/abs/2605.25028 |