The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Optimal approximation for the submodular welfare problem in the value oracle model
Abstract
In the Submodular Welfare Problem, m items are to be distributed among n players with utility functions wi: 2[m] → R+. The utility functions are assumed to be monotone and submodular. Assuming that player i receives a set of items Si, we wish to maximize the total utility ∑i=1n wi(Si). In this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning wi(S) for a given set S. Submodular Welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint: max{f(S): S ∈ I}, where f is monotone submodular and I is the collection of independent sets in some matroid.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Combinatorial optimization. Polyhedra and efficiency.
Schrijver, A. (2003) · UvA-DARE (University of Amsterdam) · Cited by 4,637
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
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
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Submodular functions and convexity
Lovász, L. (1983) · Mathematical Programming The State of the Art · doi:10.1007/978-3-642-68874-4_10 · Cited by 964
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 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 683
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
An analysis of approximations for maximizing submodular set functions—II
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978) · Mathematical Programming Studies · doi:10.1007/bfb0121195 · Cited by 589
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
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2006) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.006 · Cited by 471
Clique is hard to approximate within n/sup 1-ε/
Hastad, J. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548522 · Cited by 458
Maximizing a Submodular Set Function subject to a Matroid Constraint
Chekuri, C., Cälinescu, G., Pál, M., & Vondrák, J. (2007) · Integer Programming and Combinatorial Optimization · Cited by 367
Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee
Ageev, A. A., & Sviridenko, M. I. (2004) · Journal of Combinatorial Optimization · doi:10.1023/b:joco.0000038913.96607.c2 · Cited by 363
Combinatorial auctions with decreasing marginal utilities
Lehmann, B., Lehmann, D., & Nisan, N. (2001) · Proceedings of the 3rd ACM conference on Electronic Commerce · doi:10.1145/501158.501161 · Cited by 230
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e
Feige, U., & Vondrak, J. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.14 · Cited by 219
Self-citationTight approximation algorithms for maximum general assignment problems
Fleischer, L., Goemans, M. X., Mirrokni, V., & Sviridenko, M. I. (2006) · Cited by 218
Ambuhl, C., Mas, M., & Svensson, O. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.40 · Cited by 206
Maximum Coverage Problem with Group Budget Constraints and Applications
Chekuri, C., & Kumar, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27821-4_7 · Cited by 192
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
Calinescu, G., Chekuri, C., Pál, M., & Vondrák, J. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72792-7_15 · Cited by 187
On maximizing welfare when utility functions are subadditive
Feige, U. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132523 · Cited by 163
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
Mirrokni, V., Schapira, M., & Vondrák, J. (2008) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1386790.1386805 · Cited by 125
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions
Khot, S., Lipton, R. J., Markakis, E., & Mehta, A. (2005) · Lecture notes in computer science · doi:10.1007/11600930_10 · Cited by 94
On rectangle packing: maximizing benefits
Jansen, K., & Zhang, G. (2004) · Symposium on Discrete Algorithms · doi:10.5555/982792.982822 · Cited by 76
Cited by
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
Calinescu, G., Chekuri, C., Pál, M., & Vondrák, J. (2011) · SIAM Journal on Computing · doi:10.1137/080733991 · Cited by 795
Self-citationSubmodular Function Maximization
Krause, A., & Golovin, D. (2014) · Tractability · doi:10.1017/cbo9781139177801.004 · Cited by 751
Influence-Based Community Partition With Sandwich Method for Social Networks
Ni, Q., Guo, J., Wu, W., & Wang, H. (2023) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3148411 · Cited by 265
Information and Influence Propagation in Social Networks
Chen, W., Lakshmanan, L. V. S., & Castillo, C. (2013) · Synthesis lectures on data management · doi:10.2200/s00527ed1v01y201308dtm037 · Cited by 254
Tight Approximation Algorithms for Maximum Separable Assignment Problems
Fleischer, L., Goemans, M. X., Mirrokni, V. S., & Sviridenko, M. (2011) · Mathematics of Operations Research · doi:10.1287/moor.1110.0499 · Cited by 65
Metadata
- Authors
- Vondrak, J.
- Venue
- Proceedings of the fortieth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2008-05-17
- Pages
- 67-74
- OpenAlex
- W1989453388
- Cited by
- 546
- References
- 24
- FWCI
- 25.88
- Type
- conference paper
- 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
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.