论文标题
随机得分分类问题的两种6个6-及
Two 6-approximation Algorithms for the Stochastic Score Classification Problem
论文作者
论文摘要
我们研究未加权的随机分数分类（SSCLASS）问题的任意成本案例。我们显示了两种常数近似算法，并且两个算法都是相对于最佳自适应算法的6个及6个非自适应算法。第一种算法在三个序列之间使用了修改的旋转方法，这是受SSClass问题的单位成本案例的最新结果的启发。第二算法最初来自Gkenosis等人的工作。在我们的工作中，我们成功地将其近似因子从2（b-1）提高到6。我们的分析在大量的情况下使用了计算和函数验证之间的关系，该功能在信息理论文献中进行了研究。
We study the arbitrary cost case of the unweighted Stochastic Score Classification (SSClass) problem. We show two constant approximation algorithms and both algorithms are 6-approximation non-adaptive algorithms with respect to the optimal adaptive algorithm. The first algorithm uses a modified round-robin approach among three sequences, which is inspired by a recent result on the unit cost case of the SSClass problem. The second algorithm is originally from the work of Gkenosis et al. In our work, we successfully improve its approximation factor from 2(B-1) to 6. Our analysis heavily uses the relation between computation and verification of functions, which was studied in the information theory literature.
