Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

Abstract

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 Vondrák [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.