The Library
Monotone submodular maximization over a matroid via non-oblivious local search
Tools
Tools
Tools
Filmus, Yuval and Ward, Justin (2014) Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal on Computing, Volume 43 (Number 2). pp. 514-542. doi:10.1137/130920277 ISSN 0097-5397.
|
PDF
WRAP_Ward_1271053-cs-091214-fw-sicomp14.pdf - Published Version - Requires a PDF viewer. Download (559Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/130920277
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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Matroids, Monotone operators, Approximation theory | ||||||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||||
| ISSN: | 0097-5397 | ||||||||
| Official Date: | 27 March 2014 | ||||||||
| Dates: |
|
||||||||
| Volume: | Volume 43 | ||||||||
| Number: | Number 2 | ||||||||
| Page Range: | pp. 514-542 | ||||||||
| DOI: | 10.1137/130920277 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 28 December 2015 | ||||||||
| Date of first compliant Open Access: | 28 December 2015 | ||||||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
| Grant number: | EP/J021814/1 (EPSRC) | ||||||||
| Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
