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"

We point out an issue with one of the results in Bellala et al.[1] 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 p...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2017-11, Vol.63 (11), p.7612-7614
Main Authors: Feng Nan, Saligrama, Venkatesh
Format: Article
Language:English
Subjects:
adaptive submodular
Approximation algorithms
Decision trees
Greedy algorithms
Minimum cost
Optimization
Probability distribution
submodular
Theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We point out an issue with one of the results in Bellala et al.[1] 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 et al. about the near-optimum performance of their algorithm is also invalid.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2017.2749505