UWEE Tech Report Series

Interactive Submodular Set Cover


UWEETR-2010-0001

Author(s):
Andrew Guillory, Jeff Bilmes

Keywords:
active learning, query learning, submodular set cover

Abstract

We introduce a natural generalization of submodular 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.

Download the PDF version

Download the Gzipped Postscript version