Abstract: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.
| Subjects: | Optimization and Control (math.OC) |
| MSC classes: | 90C15 |
| Cite as: | arXiv:2605.25028 [math.OC] |
| (or arXiv:2605.25028v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25028 arXiv-issued DOI via DataCite (pending registration) |
From: Christoph Buchheim [view email]
[v1]
Sun, 24 May 2026 12:09:14 UTC (13 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。