Adaptive Submodular Optimization under Matroid Constraints

Details Adaptive Submodular Optimization under Matroid Constraints Adaptive Submodular Optimization under Matroid Constraints

2011-01-24

arxiv.org/abs/1101.4450v1

Computer Science

Data Structures and Algorithms

5 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Adaptive Submodular Optimization under Matroid Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Submodular Optimization under Matroid Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Submodular Optimization under Matroid Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-635751