{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T20:56:39Z","timestamp":1791838599363,"version":"4.3.4"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>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\u00e1k [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.<\/jats:p>","DOI":"10.1137\/130920277","type":"journal-article","created":{"date-parts":[[2014,3,27]],"date-time":"2014-03-27T12:31:41Z","timestamp":1395923501000},"page":"514-542","source":"Crossref","is-referenced-by-count":78,"title":["Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search"],"prefix":"10.1137","volume":"43","author":[{"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Justin","family":"Ward","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,3,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"atypb2","first-page":"40","author":"Alimonti P.","year":"1994","journal-title":"New York"},{"key":"atypb3","first-page":"1497","author":"Ashwinkumar B. V.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"atypb5","first-page":"649","author":"Buchbinder N.","year":"2012","journal-title":"NJ"},{"key":"atypb6","first-page":"1433","author":"Buchbinder N.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb7","first-page":"182","author":"Calinescu G.","year":"2007","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"C. Checkuri, J. Vondr\u00e1k, and R. Zenklusen,\n                      Submodular function maximization via the multilinear relaxation and contention resolution schemes\n                      , STOC, San Jose, CA, 2011.","DOI":"10.1145\/1993636.1993740"},{"key":"atypb10","first-page":"575","author":"Chekuri C.","year":"2010","journal-title":"NJ"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb13","first-page":"461","author":"Feige U.","year":"2007","journal-title":"NJ"},{"key":"atypb14","first-page":"570","author":"Feldman M.","year":"2011","journal-title":"NJ"},{"key":"atypb15","first-page":"342","author":"Feldman M.","year":"2011","journal-title":"New York"},{"key":"atypb16","first-page":"784","author":"Feldman M.","year":"2011","journal-title":"New York"},{"key":"atypb17","first-page":"601","author":"Filmus Y.","year":"2012","journal-title":"Germany"},{"key":"atypb18","first-page":"659","author":"Filmus Y.","year":"2012","journal-title":"NJ"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"Y. Filmus and J. Ward,\n                      A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint\n                      , preprint, arXiv:1204.4526, 2012.","DOI":"10.1109\/FOCS.2012.55"},{"key":"atypb20","first-page":"73","author":"Fisher M. L.","year":"1978","journal-title":"Berlin"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb22","first-page":"1098","author":"Oveis Gharan S.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"atypb24","unstructured":"P. R. Goundan and A. S. Schulz,\n                      Revisiting the Greedy Approach to Submodular Set Function Maximization\n                      , manuscript, 2007."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"atypb28","first-page":"323","author":"Lee J.","year":"2009","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-7.1.300"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"M. Sviridenko and J. Ward,\n                      Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature\n                      , preprint, arXiv:1311.4728, 2013.","DOI":"10.1137\/1.9781611973730.76"},{"key":"atypb34","first-page":"67","author":"Vondr\u00e1k J.","year":"2008","journal-title":"New York"},{"key":"atypb35","first-page":"253","author":"Vondr\u00e1k J.","year":"2010","journal-title":"Kyoto"},{"key":"atypb36","first-page":"42","author":"Ward J.","year":"2012","journal-title":"Germany"},{"key":"atypb37","unstructured":"J. Ward,\n                      Oblivious and Non-Oblivious Local Search for Combinatorial Optimization\n                      , Ph.D. thesis, University of Toronto, Toronto, 2012."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130920277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:10Z","timestamp":1787338270000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130920277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130920277"],"URL":"https:\/\/doi.org\/10.1137\/130920277","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}