{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T17:13:43Z","timestamp":1790356423060,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We consider the problem of maximizing a nonnegative submodular set function $f:2^N \\rightarrow {\\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.<\/jats:p>","DOI":"10.1137\/110839655","type":"journal-article","created":{"date-parts":[[2014,11,25]],"date-time":"2014-11-25T11:07:59Z","timestamp":1416913679000},"page":"1831-1879","source":"Crossref","is-referenced-by-count":127,"title":["Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes"],"prefix":"10.1137","volume":"43","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,11,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1011"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , 3rd ed., John Wiley & Sons, Hoboken, NJ, 2008.","DOI":"10.1002\/9780470277331"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a024"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000816"},{"key":"atypb6","first-page":"182","author":"Calinescu G.","year":"2007","journal-title":"Berlin"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1210-5"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9417-5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90048-7"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. Hartline, D. Malec, and B. Sivan,\n                      Sequential Posted Pricing and Multi-Parameter Mechanism Design\n                      , preprint, arXiv:0907.2435v1 [cs.GT], 2009.","DOI":"10.1145\/1807406.1807428"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. Hartline, D. Malec, and B. Sivan,\n                      Multi-parameter mechanism design and sequential posted pricing\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 311-320.","DOI":"10.1145\/1806689.1806733"},{"key":"atypb13","first-page":"42","author":"Chekuri C.","year":"2009","journal-title":"Heidelberg"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273343"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"C. Chekuri, J. Vondr\u00e1k, and R. Zenklusen,\n                      Dependent randomized rounding via exchange properties of combinatorial structures\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 575-584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1145\/1993636.1993740","author":"Chekuri C.","year":"2011","journal-title":"Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"atypb18","first-page":"11","author":"Ene A.","year":"2012","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Vondr\u00e1k,\n                      Approximation algorithms for allocation problems: Improving the factor of $1-1\/e$\n                      , in Proceedings of the $47$th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 667-676.","DOI":"10.1109\/FOCS.2006.14"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a011"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. Feldman, J. Naor, and R. Schwartz,\n                      A unified continuous greedy algorithm for submodular maximization\n                      , in Proceedings of the $52$nd Annual IEEE Symposium on Foundations of Computer Science, 2011, pp. 570-579.","DOI":"10.1109\/FOCS.2011.46"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"atypb27","unstructured":"A. Gupta, V. Nagarajan, and R. Ravi,\n                      Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets\n                      , preprint, http:\/\/arxiv.org\/abs\/1012.4962arXiv:1012.4962v2 [cs.DS], 2011."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Roth, G. Schoenebeck, and K. Talwar,\n                      Constrained non-monotone submodular maximization: Offline and secretary algorithms\n                      , in Proceedings of the 6th International Conference on Internet and Network Economics, Springer-Verlag, Berlin, Heidelberg, 2010.","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"atypb29","unstructured":"A. Gupta, A. Roth, G. Schoenebeck, and K. Talwar,\n                      Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms\n                      , preprint, http:\/\/arxiv.org\/abs\/1003.1517arXiv:1003.1517v2 [cs.DS], 2010."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"B. Korte and J. Vygen,\n                      Combinatorial Optimization: Theory and Algorithms\n                      , Springer, Heidelberg, 2012.","DOI":"10.1007\/978-3-642-24488-9"},{"key":"atypb33","first-page":"545","author":"Kulik A.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/11083232X"},{"key":"atypb38","first-page":"235","author":"Lov\u00e1sz L.","year":"1983","journal-title":"Berlin"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"V. Mirrokni, M. Schapira, and J. Vondr\u00e1k,\n                      Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions\n                      , in Proceedings of the 9th ACM Conference on Electronic Commerce, 2008, pp. 70-77.","DOI":"10.1145\/1386790.1386805"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"atypb42","first-page":"1098","author":"Oveis Gharan S.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb43","first-page":"567","author":"Srinivasan A.","year":"2001","journal-title":"Philadelphia"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"atypb45","unstructured":"J. Vondr\u00e1k,\n                      Submodularity in Combinatorial Optimization\n                      , Ph.D. thesis, Department of Applied Mathematics, Charles University, Prague, Czech Republic, 2007."},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"J. Vondr\u00e1k,\n                      Optimal approximation for the submodular welfare problem in the value oracle model\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 67-74.","DOI":"10.1145\/1374376.1374389"},{"key":"atypb47","unstructured":"J. Vondr\u00e1k,\n                      A Note on Concentration of Submodular Functions\n                      , preprint, http:\/\/arxiv.org\/abs\/1005.2791arXiv:1005.2791v1 http:\/\/arxiv.org\/abs\/1005.2791[cs.DM], 2010."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"},{"key":"atypb49","first-page":"710","author":"Yan Q.","year":"2011","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110839655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:10:35Z","timestamp":1787339435000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110839655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/110839655"],"URL":"https:\/\/doi.org\/10.1137\/110839655","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}