Title :
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Author :
Filmus, Yuval ; Ward, Justin
Author_Institution :
Dept. of Comput. Sci., Univ. of Toronto, Toronto, ON, Canada
Abstract :
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone sub modular 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 sub modular. In our previous work on maximum coverage (Filmus and Ward, 2011), the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone sub modular functions. When the objective function is a coverage function, both definitions of the potential function coincide. The parameters used to define the potential function are closely related to Pade approximants of exp(x) evaluated at x = 1. We use this connection to determine the approximation ratio of the algorithm.
Keywords :
approximation theory; combinatorial mathematics; functions; greedy algorithms; matrix algebra; optimisation; search problems; Pade approximants; approximation ratio; coverage functions; greedy algorithm; local search; matroid constraint; monotone submodular optimization; nonoblivious potential function; optimal combinatorial 1-1/e approximation algorithm; potential function coincide; submodular maximization; tight combinatorial algorithm; Algorithm design and analysis; Approximation algorithms; Approximation methods; Greedy algorithms; Linear programming; Search problems; approximation algorithms; local search; matroids; submodular functions;
Conference_Titel :
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
978-1-4673-4383-1
DOI :
10.1109/FOCS.2012.55