论文标题
与近似值较小的随机评分分类的简单算法
Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
论文作者
论文摘要
我们重新审查了Gkenisoise等人引入的随机评分分类（SSC）问题。 （ESA 2018）：我们获得了$ N $测试。每个测试$ j $都可以以$ C_J $的价格进行，并且概率$ p_j $独立成功。此外，已知的（整数）间隔$ \ {0，\ dots，n \} $的分区已知。目的是进行测试，以确定成功测试数量的分区间隔，同时最大程度地减少预期成本。 Ghuge等。 （IPCO 2022）最近表明，多项式恒定因素近似算法存在。 我们表明，正如Gkensosis等人已经提出的那样，分别通过$ C_J/P_J $和$ C_J/（1-P_J）$比率进行订购的两种策略，分别通过其$ C_J/P_J/（1-P_J）$。对于特殊情况 - 产生较小的近似值。我们还表明，近似值可以从$ 6 $略微降低到$ 3+2 \ 2 \ sqrt {2} \大约5.828 $，通过添加第三个策略，该策略简单地按照其成本订购了测试。两种算法的类似分析都是不平凡的，但可以说是干净的。最后，我们在自适应间隙上以$ 3/2 $的下限为$ 3+2 \ sqrt {2} $的隐含上限。由于较低的实例是一个所谓的单位成本$ k $ - $ n $实例，因此在这种情况下，我们解决了适应性差距。
We revisit the Stochastic Score Classification (SSC) problem introduced by Gkenosis et al. (ESA 2018): We are given $n$ tests. Each test $j$ can be conducted at cost $c_j$, and it succeeds independently with probability $p_j$. Further, a partition of the (integer) interval $\{0,\dots,n\}$ into $B$ smaller intervals is known. The goal is to conduct tests so as to determine that interval from the partition in which the number of successful tests lies while minimizing the expected cost. Ghuge et al. (IPCO 2022) recently showed that a polynomial-time constant-factor approximation algorithm exists. We show that interweaving the two strategies that order tests increasingly by their $c_j/p_j$ and $c_j/(1-p_j)$ ratios, respectively, -- as already proposed by Gkensosis et al. for a special case -- yields a small approximation ratio. We also show that the approximation ratio can be slightly decreased from $6$ to $3+2\sqrt{2}\approx 5.828$ by adding in a third strategy that simply orders tests increasingly by their costs. The similar analyses for both algorithms are nontrivial but arguably clean. Finally, we complement the implied upper bound of $3+2\sqrt{2}$ on the adaptivity gap with a lower bound of $3/2$. Since the lower-bound instance is a so-called unit-cost $k$-of-$n$ instance, we settle the adaptivity gap in this case.
