Journal
SIAM JOURNAL ON COMPUTING
Volume 43, Issue 2, Pages 514-542Publisher
SIAM PUBLICATIONS
DOI: 10.1137/130920277
Keywords
approximation algorithms; submodular functions; matroids; local search
Funding
- EPSRC [EP/J021814/1]
- Engineering and Physical Sciences Research Council [EP/J021814/1] Funding Source: researchfish
Ask authors/readers for more resources
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm [G. Calinescu et al., IPCO, Springer, Berlin, 2007, pp. 182-196] our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by a local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage [Y. Filmus and J. Ward, FOCS, IEEE, Piscataway, NJ, 2012, pp. 659-668], the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. 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 matches results of Vondrak [STOC, ACM, New York, 2008, pp. 67-74], who has shown that the continuous greedy algorithm produces a (1 - e(-c))/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available