{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T05:40:26Z","timestamp":1792129226775,"version":"4.4.0"},"reference-count":45,"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":[[2011,1]]},"abstract":"<jats:p>Let $f:2^X \\rightarrow \\cal R_+$ be a monotone submodular set function, and let $(X,\\cal I)$ be a matroid. We consider the problem ${\\rm max}_{S \\in \\cal I} f(S)$. It is known that the greedy algorithm yields a $1\/2$-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73\u201387] for this problem. For certain special cases, e.g., ${\\rm max}_{|S| \\leq k} f(S)$, the greedy algorithm yields a $(1-1\/e)$-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning $f(S)$ for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177\u2013188] and for explicitly posed instances assuming $P \\neq NP$ [U. Feige, J. ACM, 45 (1998), pp. 634\u2013652]. In this paper, we provide a randomized $(1-1\/e)$-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307\u2013328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondr\u00e1k, Proceedings of the $38$th ACM Symposium on Theory of Computing, 2008, pp. 67\u201374]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires $|X|$ to be exponential in the original problem size, we are able to achieve a $(1-1\/e-o(1))$-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.<\/jats:p>","DOI":"10.1137\/080733991","type":"journal-article","created":{"date-parts":[[2011,12,22]],"date-time":"2011-12-22T10:05:42Z","timestamp":1324548342000},"page":"1740-1766","source":"Crossref","is-referenced-by-count":541,"title":["Maximizing a Monotone Submodular Function Subject to a Matroid Constraint"],"prefix":"10.1137","volume":"40","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,22]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley Interscience, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"G. Calinescu, C. Chekuri, M. P\u00e1l, and J. Vondr\u00e1k,\n                      Maximizing a submodular set function subject to a matroid constraint\n                      , in Proceedings of the 12th IPCO Conference, 2007, pp. 182\u2013196.","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1020-3"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty and G. Goel,\n                      On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 687\u2013696.","DOI":"10.1109\/FOCS.2008.47"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"C. Chekuri and A. Kumar,\n                      Maximum coverage problem with group budget constraints and applications\n                      , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3122, Springer, Berlin, 2004, pp. 72\u201383.","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. Chekuri and M. P\u00e1l,\n                      A recursive greedy algorithm for walks in directed graphs\n                      , in Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 2005, pp. 245\u2013253.","DOI":"10.1109\/SFCS.2005.9"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90023-6"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Dobzinski and M. Schapira,\n                      An improved approximation algorithm for combinatorial auctions with submodular bidders\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1064\u20131073.","DOI":"10.1145\/1109557.1109675"},{"key":"R12","unstructured":"J. Edmonds,\n                      Submodular functions, matroids, and certain polyhedra\n                      , in Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 69\u201387."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      On maximizing welfare when utility functions are subadditive\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 41\u201350.","DOI":"10.1145\/1132516.1132523"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"U. Feige, V. Mirrokni, and J. Vondr\u00e1k,\n                      Maximizing a non-monotone submodular function\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 461\u2013471.","DOI":"10.1109\/FOCS.2007.29"},{"key":"R16","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 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 667\u2013676.","DOI":"10.1109\/FOCS.2006.14"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey,\n                      An analysis of approximations for maximizing submodular set functions.\n                      II., Math. Programming Stud., no. 8 (1978), pp. 73\u201387.","DOI":"10.1007\/BFb0121195"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko,\n                      Tight approximation algorithms for maximum general assignment problems\n                      , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 611\u2013620.","DOI":"10.1145\/1109557.1109624"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"R21","unstructured":"P. Goundan and A. Schulz,\n                      Revisiting the Greedy Approach to Submodular Set Function Maximization\n                      , manuscript, 2007."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, Berlin, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"E. Hazan, S. Safra, and O. Schwartz,\n                      \n                        On the complexity of approximating\n                        k\n                        -set packing\n                      \n                      , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 2764, Springer, Berlin, 2003, pp. 83\u201397.","DOI":"10.1007\/978-3-540-45198-3_8"},{"key":"R25","unstructured":"T. A. Jenkyns,\n                      The efficacy of the \u201cgreedy\u201d algorithm\n                      , in Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1976, pp. 341\u2013350."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9105-7"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. Kulik, H. Shachnai, and T. Tamir,\n                      Maximizing submodular functions subject to multiple linear constraints\n                      , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 545\u2013554.","DOI":"10.1137\/1.9781611973068.60"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"J. Lee, V. Mirrokni, V. Nagarajan, and M. Sviridenko,\n                      Non-monotone submodular maximization under matroid and knapsack constraints\n                      , in Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 323\u2013332.","DOI":"10.1145\/1536414.1536459"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. Lee, M. Sviridenko, and J. Vondr\u00e1k,\n                      Submodular maximization over multiple matroids via generalized exchange properties\n                      , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 5687, Springer, Berlin, 2009, pp. 244\u2013257.","DOI":"10.1007\/978-3-642-03685-9_19"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"J. Mestre,\n                      Greedy in approximation algorithms\n                      , in Proceedings of the 14th European Symposium on Algorithms, Springer, Berlin, 2006, pp. 528\u2013539.","DOI":"10.1007\/11841036_48"},{"key":"R34","unstructured":"J. Mestre,\n                      private communication\n                      , 2008."},{"key":"R35","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 ACM Conference on Electronic Commerce, 2008, pp. 70\u201377.","DOI":"10.1145\/1386790.1386805"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"R39","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\u2014Polyhedra and Efficiency\n                      , Springer, Berlin, 2003."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"A. Srinivasan,\n                      Distributions on level-sets with applications to approximation algorithms\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 588\u2013597.","DOI":"10.1109\/SFCS.2001.959935"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"R42","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 ACM Symposium on Theory of Computing, 2008, pp. 67\u201374.","DOI":"10.1145\/1374376.1374389"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"J. Vondr\u00e1k,\n                      Symmetry and approximability of submodular maximization problems\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 651\u2013670.","DOI":"10.1109\/FOCS.2009.24"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.3.410"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080733991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:12Z","timestamp":1787337192000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080733991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/080733991"],"URL":"https:\/\/doi.org\/10.1137\/080733991","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}