CoChat
Sign Up
Cited by 795Complexity and Algorithms in GraphsOptimization and Search ProblemsGame Theory and Voting Systems

The DOI matches its Crossref record; its reference list is not available.

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

Calinescu, Gruia, Chekuri, Chandra, Pál, Martin, Vondrák, Jan·2011·SIAM Journal on Computing
DOI 10.1137/080733991
Open this paper in CoChat — free account

Abstract

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–87] 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–188] and for explicitly posed instances assuming $P \neq NP$ [U. Feige, J. ACM, 45 (1998), pp. 634–652]. 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–328], 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ák, Proceedings of the $38$th ACM Symposium on Theory of Computing, 2008, pp. 67–74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although…

Overview

Integrity signals

Registry

Crossref · 10.1137/080733991

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 42 · Cited by 795

Research works printed but not linked: 43

  1. 10.1023/B:JOCO.0000038913.96607.c2 · DOI
  2. N. Alon and J. H. Spencer, The Probabilistic Method , 2nd ed., Wiley Interscience, New York, 2000. · DOI
  3. G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint , in Proceedings of the 12th IPCO Conference, 2007, pp. 182–196. · DOI
  4. 10.1007/s00453-002-1020-3 · DOI
  5. D. Chakrabarty and G. Goel, On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 687–696. · DOI
  6. 10.1137/S0097539700382820 · DOI
  7. C. Chekuri and A. Kumar, Maximum coverage problem with group budget constraints and applications , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 3122, Springer, Berlin, 2004, pp. 72–83. · DOI
  8. C. Chekuri and M. Pál, A recursive greedy algorithm for walks in directed graphs , in Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 2005, pp. 245–253. · DOI
  9. 10.1287/mnsc.23.8.789 · DOI
  10. 10.1016/0095-8956(84)90023-6 · DOI
  11. S. Dobzinski and M. Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1064–1073. · DOI
  12. J. Edmonds, Submodular functions, matroids, and certain polyhedra , in Combinatorial Structures and Their Applications, Gordon and Breach, New York, 1970, pp. 69–87.
  13. 10.1145/285055.285059 · DOI
  14. U. Feige, On maximizing welfare when utility functions are subadditive , in Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 41–50. · DOI
  15. U. Feige, V. Mirrokni, and J. Vondrák, Maximizing a non-monotone submodular function , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 461–471. · DOI
  16. U. Feige and J. Vondrák, Approximation algorithms for allocation problems: Improving the factor of $1-1/e$ , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 667–676. · DOI
  17. M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, An analysis of approximations for maximizing submodular set functions. II., Math. Programming Stud., no. 8 (1978), pp. 73–87. · DOI · Paper page
  18. 10.1145/502090.502096 · DOI
  19. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko, Tight approximation algorithms for maximum general assignment problems , in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 611–620. · DOI
  20. 10.1145/1147954.1147956 · DOI
  21. 10.1002/j.1538-7305.1966.tb01709.x · DOI
  22. M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization , Springer, Berlin, 1988. · DOI
  23. E. Hazan, S. Safra, and O. Schwartz, On the complexity of approximating k -set packing , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 2764, Springer, Berlin, 2003, pp. 83–97. · DOI
  24. T. A. Jenkyns, The efficacy of the “greedy” algorithm , in Proceedings of the 7th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1976, pp. 341–350.
  25. 10.1007/s00453-007-9105-7 · DOI
  26. 10.1016/S0020-0190(99)00031-9 · DOI
  27. 10.1016/S0167-5060(08)70322-4 · DOI
  28. A. Kulik, H. Shachnai, and T. Tamir, Maximizing submodular functions subject to multiple linear constraints , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 545–554. · DOI
  29. J. Lee, V. Mirrokni, V. Nagarajan, and M. Sviridenko, Non-monotone submodular maximization under matroid and knapsack constraints , in Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 323–332. · DOI
  30. J. Lee, M. Sviridenko, and J. Vondrák, Submodular maximization over multiple matroids via generalized exchange properties , in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 5687, Springer, Berlin, 2009, pp. 244–257. · DOI
  31. 10.1016/j.geb.2005.02.006 · DOI
  32. J. Mestre, Greedy in approximation algorithms , in Proceedings of the 14th European Symposium on Algorithms, Springer, Berlin, 2006, pp. 528–539. · DOI
  33. V. Mirrokni, M. Schapira, and J. Vondrák, Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions , in Proceedings of the ACM Conference on Electronic Commerce, 2008, pp. 70–77. · DOI
  34. 10.1287/moor.3.3.177 · DOI · Paper page
  35. 10.1007/BF01588971 · DOI · Paper page
  36. 10.1006/jctb.2000.1989 · DOI
  37. A. Schrijver, Combinatorial Optimization—Polyhedra and Efficiency , Springer, Berlin, 2003.
  38. A. Srinivasan, Distributions on level-sets with applications to approximation algorithms , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 588–597. · DOI
  39. 10.1016/S0167-6377(03)00062-2 · DOI
  40. J. Vondrák, Optimal approximation for the submodular welfare problem in the value oracle model , in Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 67–74. · DOI
  41. J. Vondrák, Symmetry and approximability of submodular maximization problems , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 651–670. · DOI
  42. 10.1007/BF02579435 · DOI
  43. 10.1287/moor.7.3.410 · DOI

Metadata

Authors
Calinescu, G., Chekuri, C., Pál, M., & Vondrák, J.
ORCID
Venue
SIAM Journal on Computing
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Published
2011-01
Volume
40
Issue
6
Pages
1740-1766
ISSN
  • 0097-5397 (ISSN-L)
  • 1095-7111
DOI
10.1137/080733991
OpenAlex
W2132651631
Cited by
795
References
42
Citations by year
2026: 34 · 2025: 41 · 2024: 50 · 2023: 58 · 2022: 58 · 2021: 78 · 2020: 83 · 2019: 74 · 2018: 76 · 2017: 51 · 2016: 40 · 2015: 45 · 2014: 36 · 2013: 29 · 2012: 17
FWCI
28.93
Type
journal article
Language
en
Open access
closed
Locations
SIAM Journal on Computing (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
Keywords
submodular maximization, matroid constraints, randomized approximation, generalized assignment problem, approximation algorithms, monotone submodular functions, combinatorial optimization, set functions

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review