Comments on the Proof of Adaptive Stochastic Set Cover Based on Adaptive Submodularity and Its Implications for the Group Identification Problem in “Group-Based Active Query Selection for Rapid Diagnosis in Time-Critical Situations”
Comments on the Proof of Adaptive Stochastic Set Cover Based on Adaptive Submodularity and Its Implications for the Group Identification Problem in “Group-Based Active Query Selection for Rapid Diagnosis in Time-Critical Situations”
复制标题
《基于组的主动查询选择在时间关键情况下快速诊断》中评述基于自适应子模性的自适应随机集合覆盖的证明及其对组识别问题的启示
DOI：
10.1109/tit.2017.2749505
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
Venkatesh Saligrama
中科院分区：
文献类型：
--
作者：
Feng Nan;Venkatesh Saligrama
我们指出Bellala <italic>et al.</italic> <xref ref-type="bibr" rid="ref1">[1]</xref>的一个结果中的一个问题，该结果引用了Golovin和Krause关于自适应随机最小成本覆盖问题（定理5.8）的一个主要结果。我们构造了一个例子，证明了Golovin和Krause的定理5.8的证明是无效的，因此，Bellala <italic>等人</italic>中关于其算法接近最优性能的证明也是无效的。
We point out an issue with one of the results in Bellala <italic>et al.</italic> <xref ref-type="bibr" rid="ref1">[1]</xref> that invokes a main result on adaptive stochastic minimum cost cover problem (Theorem 5.8) of Golovin and Krause. We construct an example that shows that the proof of Theorem 5.8 of Golovin and Krause is invalid, and therefore, the proof in Bellala <italic>et al.</italic> about the near-optimum performance of their algorithm is also invalid.