




















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。