论文标题
有效的近似方案，用于随机探测和选择问题
Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
论文作者
论文摘要
在本文中，我们提出了一个通用框架，以设计{有效}多项式时间近似方案（EPTA），以解决基本的随机组合优化问题。给定错误参数$ε> 0 $，此类算法方案达到了$（1-ε）$ - 近似$ t（ε）\ cdot poly（| {\ cal i} |）$ time，其中$ t（\ cdot）$仅取决于$ t（\ cdot）$仅取决于$ $ the $ the $ the $ε$和$ε$ | {\ cal i} $ cal i} | $ decut。从技术上讲，我们的方法依赖于将量身定制的减少介绍给新引入的多维圣诞老人问题。即使已知该问题的单维版本已经是APX-HARD，但我们证明EPTA可以为恒定数量的机器和尺寸设计，这些机器和尺寸适用于我们的每个应用程序。 为了证明我们的框架的多功能性，我们首先研究了选择的设置，以推导自由订购先知问题的EPTA [Agrawal等人，EC〜 '20]，以及其成本驱动的概括，Pandora的盒子以承诺[Fu等人，ICALP〜 '18]。 These results constitute the first approximation schemes in the non-adaptive setting and improve on known \emph{inefficient} polynomial time approximation schemes (PTAS) for their adaptive variants.接下来，将注意力转向随机探测问题，我们为自适应探针问题及其非自适应对应物获得了EPTA。在这两种情况下，最新的近似性结果都是效率低下的Ptases [Chen等，Nips〜 '16; Fu等人，ICALP〜 '18]。
In this paper, we propose a general framework to design {efficient} polynomial time approximation schemes (EPTAS) for fundamental stochastic combinatorial optimization problems. Given an error parameter $ε>0$, such algorithmic schemes attain a $(1-ε)$-approximation in $t(ε)\cdot poly(|{\cal I}|)$ time, where $t(\cdot)$ is a function that depends only on $ε$ and $|{\cal I}|$ denotes the input length. Technically speaking, our approach relies on presenting tailor-made reductions to a newly-introduced multi-dimensional 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 Free-Order Prophets problem [Agrawal et al., EC~'20] and for its cost-driven generalization, Pandora's Box with Commitment [Fu et al., ICALP~'18]. These results constitute the first approximation schemes in the non-adaptive setting and improve on known \emph{inefficient} polynomial time approximation schemes (PTAS) 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 non-adaptive counterpart; in both cases, state-of-the-art approximability results have been inefficient PTASes [Chen et al., NIPS~'16; Fu et al., ICALP~'18].
