Adaptive Submodular Optimization under Matroid Constraints

Abstract

Many important problems in discrete optimization require maximization of a monotonic submodular function subject to matroid constraints. For these problems, a simple greedy algorithm is guaranteed to obtain near-optimal solutions. In this article, we extend this classic result to a general class of adaptive optimization problems under partial observability, where each choice can depend on observations resulting from past choices. Specifically, we prove that a natural adaptive greedy algorithm provides a $1/(p+1)$ approximation for the problem of maximizing an adaptive monotone submodular function subject to $p$ matroid constraints, and more generally over arbitrary $p$-independence systems. We illustrate the usefulness of our result on a complex adaptive match-making application.

5 pages

References in corpus (2)

• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
• Near-Optimal Bayesian Active Learning with Noisy Observations

Cited by in corpus (8)

• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
• Approximation Algorithms for Bayesian Multi-Armed Bandit Problems
• Adaptive Influence Maximization in Social Networks: Why Commit when You can Adapt?
• On maximizing a monotone k-submodular function subject to a matroid constraint
• Linear-Time Algorithms for Adaptive Submodular Maximization
• The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization
• Robust Adaptive Submodular Maximization