Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems

• 成果类型: Article; Early Access
• 署名作者: Segev, Danny; Singla, Sahil
• 署名单位: Tel Aviv University; Tel Aviv University; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2023.0242
• 发表日期: 2025-12-11
• 关键词: stochastic combinatorial optimization; approximation schemes; load balancing; optimal stopping; Pandora's box; combinatorial auctions; prophet inequalities; IMPROVED BOUNDS; SECRETARY; Knapsack

摘要

In this paper, we propose a general framework to design efficient polynomialtime approximation schemes (EPTASs) for fundamental stochastic combinatorial optimization problems. Technically speaking, our approach relies on presenting tailor-made reductions to a newly introduced multidimensional Santa Claus problem. Even though the single-dimensional version of this problem is already known to be APX-Hard, we prove that an EPTAS can be designed for a constant number of machines and dimensions, which hold for each of our applications. To demonstrate the versatility of our framework, we first study selection-stopping settings to derive an EPTAS for the freeorder prophets problem and for its cost-driven generalization, Pandora's box with commitment. These results constitute the first approximation schemes in the nonadaptive setting and improve on known inefficient polynomial-time approximation schemes (PTASs) for their adaptive variants. Next, turning our attention to stochastic probing problems, we obtain an EPTAS for the adaptive ProbeMax problem as well as for its nonadaptive counterpart. In both cases, state-of-the-art approximability results have been inefficient PTASs (Chen et al. [25], Fu et al. [35]).