The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Maximizing Non-monotone Submodular Functions
Abstract
Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper, we design the first constant-factor approximation algorithms for maximizing nonnegative (non-monotone) submodular functions. In particular, we give a deterministic local-search $\frac{1}{3}$-approximation and a randomized $\frac{2}{5}$-approximation algorithm for maximizing nonnegative submodular functions. We also show that a uniformly random set gives a $\frac{1}{4}$-approximation. For symmetric submodular functions, we show that a random set gives a $\frac{1}{2}$-approximation, which can also be achieved by deterministic local search. These algorithms work in the value oracle model, where the submodular function is accessible through a black box returning $f(S)$ for a given set S. We show that in this model, a $(\frac{1}{2}+\epsilon)$-approximation for symmetric submodular functions would require an exponential number of queries for any fixed $\epsilon>0$. In the model where f is given explicitly (as a sum of nonnegative submodular functions, each depending only on a constant number of elements), we prove NP-hardness of $(\frac{5}{6}+\epsilon)$-approximation in the symmetric case and NP-hardness of $(\frac{3}{4}+\epsilon)$-approximation in the general case.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
Self-citationSome optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Cornuejols, G., Fisher, M. L., & Nemhauser, G. L. (1977) · Management Science · doi:10.1287/mnsc.23.8.789 · Cited by 793
A note on maximizing a submodular set function subject to a knapsack constraint
Sviridenko, M. (2004) · Operations Research Letters · doi:10.1016/s0167-6377(03)00062-2 · Cited by 690
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
Schrijver, A. (2000) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.2000.1989 · Cited by 651
A combinatorial strongly polynomial algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (2001) · Journal of the ACM · doi:10.1145/502090.502096 · Cited by 561
Best Algorithms for Approximating the Maximum of a Submodular Set Function
Nemhauser, G. L., & Wolsey, L. A. (1978) · Mathematics of Operations Research · doi:10.1287/moor.3.3.177 · Cited by 538
Simple Local Search Problems that are Hard to Solve
Schäffer, A. A. (1991) · SIAM Journal on Computing · doi:10.1137/0220004 · Cited by 291
Cited by
Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing
Yang, D., Xue, G., Fang, X., & Tang, J. (2012) · Proceedings of the 18th annual international conference on Mobile computing and networking · doi:10.1145/2348543.2348567 · Cited by 997
Interpretable Decision Sets: A Joint Framework for Description and Prediction
Lakkaraju, H., Bach, S. H., & Leskovec, J. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939874 · Cited by 687
Dong, X. L., & Srivastava, D. (2015) · Synthesis Lectures on Data Management · doi:10.1007/978-3-031-01853-4 · Cited by 539
Incentives for Mobile Crowd Sensing: A Survey
Zhang, X., Yang, Z., Sun, W., Liu, Y., Tang, S., Xing, K., & Mao, X. (2016) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2415528 · Cited by 515
Incentive Mechanisms for Crowdsensing: Crowdsourcing With Smartphones
Yang, D., Xue, G., Fang, X., & Tang, J. (2016) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2015.2421897 · Cited by 439
Metadata
- Authors
- Feige, U., Mirrokni, V. S., & Vondrák, J.
- Venue
- SIAM Journal on Computing
- Published
- 2011-01
- Volume
- 40
- Issue
- 4
- Pages
- 1133-1153
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2053381548
- Cited by
- 452
- References
- 12
- FWCI
- 17.94
- Type
- journal article
- Language
- en
- Open access
- closed
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Maximizing Non-monotone Submodular Functions. https://app.cochat.ai/papers/10.1137/090779346
- The paper
- Feige, U., Mirrokni, V. S., & Vondrák, J. (2011). Maximizing Non-monotone Submodular Functions. SIAM Journal on Computing. https://doi.org/10.1137/090779346
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.