Interactive Submodular Set Cover
Abstract
We introduce a natural generalization of sub-modular set cover and exact active learning with a finite hypothesis class (query learning). We call this new problem interactive submodular set cover. Applications include advertising in social networks with hidden information. We give an approximation guarantee for a novel greedy algorithm and give a hardness of approximation result which matches up to constant factors. We also discuss negative results for simpler approaches and present encouraging early experimental results.
Cite
Text
Guillory and Bilmes. "Interactive Submodular Set Cover." International Conference on Machine Learning, 2010.Markdown
[Guillory and Bilmes. "Interactive Submodular Set Cover." International Conference on Machine Learning, 2010.](https://mlanthology.org/icml/2010/guillory2010icml-interactive/)BibTeX
@inproceedings{guillory2010icml-interactive,
title = {{Interactive Submodular Set Cover}},
author = {Guillory, Andrew and Bilmes, Jeff A.},
booktitle = {International Conference on Machine Learning},
year = {2010},
pages = {415-422},
url = {https://mlanthology.org/icml/2010/guillory2010icml-interactive/}
}