A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

Details A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

2012-04-20

arxiv.org/abs/1204.4526v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Calinescu, Chekuri, Pal and Vondrak, 2008), our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by local search. Both phases are run not on the actual objective function, but on a related non-oblivious potential function, which is also monotone submodular. Our algorithm runs in randomized time O(n^8u), where n is the rank of the given matroid and u is the size of its ground set. We additionally obtain a 1-1/e-eps approximation algorithm running in randomized time O (eps^-3n^4u). For matroids in which n = o(u), this improves on the runtime of the continuous greedy algorithm. The improvement is due primarily to the time required by the pipage rounding phase, which we avoid altogether. Furthermore, the independence of our algorithm from pipage rounding techniques suggests that our general approach may be helpful in contexts such as monotone submodular maximization subject to multiple matroid constraints. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1-e^-c)/c approximation. This result complements results of Vondrak (2008), who has shown that the continuous greedy algorithm produces a (1-e^-c)/c approximation when the objective function has curvature c. He has also proved that achieving any better approximation ratio is impossible in the value oracle model.

Affiliated with

Also associated with

No associations

Rating

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint 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 A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-5210