by ,
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.
Reference:
Adaptive Submodular Optimization under Matroid Constraints D. Golovin, A. KrauseTechnical report, arXiv, 2011
Bibtex Entry:
@techreport{golovin11matroid,
	Author = {Daniel Golovin and Andreas Krause},
	Institution = {arXiv},
	Title = {Adaptive Submodular Optimization under Matroid Constraints},
	Year = {2011}}