Interactive Submodular Set Cover
arXiv:1002.3345
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.
15 pages, 1 figure
Cited by in corpus (11)
- Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
- Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
- Using Error Decay Prediction to Overcome Practical Issues of Deep Active Learning for Named Entity Recognition
- Batched Stochastic Bayesian Optimization via Combinatorial Constraints Design
- Adaptivity in Adaptive Submodularity
- Interactive algorithms: from pool to stream
- Maximizing Stochastic Monotone Submodular Functions
- Continuous Submodular Maximization: Beyond DR-Submodularity
- Minimum Entropy Submodular Optimization (and Fairness in Cooperative Games)
- Robust Adaptive Submodular Maximization
- Max-Cost Discrete Function Evaluation Problem under a Budget