Adaptive Submodular Optimization under Matroid Constraints

Understand

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.