The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
A threshold of ln n for approximating set cover
Open accessAbstract
Given a collection ℱ of subsets of S = {1,…, n }, set cover is the problem of selecting as few as possible subsets from ℱ such that their union covers S, , and max k-cover is the problem of selecting k subsets from ℱ such that their union has maximum cardinality. Both these problems are NP-hard. We prove that (1 - o (1)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low-order terms) between the ratio of approximation achievable by the greedy alogorithm (which is (1 - o (1)) ln n), and provious results of Lund and Yanakakis, that showed hardness of approximation within a ratio of (log 2 n ) / 2 ≃0.72 ln n . For max k -cover, we show an approximation threshold of (1 - 1/ e )(up to low-order terms), under assumption that P ≠ NP .
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
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
A Greedy Heuristic for the Set-Covering Problem
Chvatal, V. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.3.233 · Cited by 2,581
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Cited by
"Why Should I Trust You?": Explaining the Predictions of Any Classifier
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939778 · Cited by 17,555
“Why Should I Trust You?”: Explaining the Predictions of Any Classifier
Ribeiro, M., Singh, S., & Guestrin, C. (2016) · Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Demonstrations · doi:10.18653/v1/n16-3020 · Cited by 6,682
Automatic subspace clustering of high dimensional data for data mining applications
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276314 · Cited by 2,412
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Scalable influence maximization for prevalent viral marketing in large-scale social networks
Chen, W., Wang, C., & Wang, Y. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835934 · Cited by 1,731
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
FastText.zip: Compressing text classification models
Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., & Mikolov, T. (2016) · arXiv · doi:10.48550/arxiv.1612.03651 · Cited by 887
On the power of unique 2-prover 1-round games
Khot, S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.510017 · Cited by 818
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
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 753
Submodular Function Maximization
Krause, A., & Golovin, D. (2014) · Tractability · doi:10.1017/cbo9781139177801.004 · Cited by 751
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
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
On the hardness of approximating vertex cover
Dinur, I., & Safra, S. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.162.439 · Cited by 636
Korte, B., & Vygen, J. (2000) · Algorithms and Combinatorics · doi:10.1007/978-3-662-21708-5_16 · Cited by 579
PARAMETERIZED COMPLEXITY THEORY
Niedermeier, R. (2006) · Invitation to Fixed-Parameter Algorithms · doi:10.1093/acprof:oso/9780198566076.003.0013 · Cited by 574
Beyond Independent Relevance: Methods and Evaluation Metrics for Subtopic Retrieval
Zhai, C., Cohen, W. W., & Lafferty, J. (2015) · ACM SIGIR Forum · doi:10.1145/2795403.2795405 · Cited by 558
(2016) · neural information processing systems · Cited by 556
Optimal approximation for the submodular welfare problem in the value oracle model
Vondrak, J. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374389 · Cited by 546
Determinantal Point Processes for Machine Learning
Kulesza, A. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986290 · Cited by 493
On Submodularity and Controllability in Complex Dynamical Networks
Summers, T. H., Cortesi, F. L., & Lygeros, J. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2453711 · Cited by 482
Suggestive Annotation: A Deep Active Learning Framework for Biomedical Image Segmentation
Yang, L., Zhang, Y., Chen, J., Zhang, S., & Chen, D. Z. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-66179-7_46 · Cited by 480
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Golovin, D., & Krause, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.3967 · Cited by 461
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Maximizing Non-monotone Submodular Functions
Feige, U., Mirrokni, V. S., & Vondrák, J. (2011) · SIAM Journal on Computing · doi:10.1137/090779346 · Cited by 452
Self-citationAnalytical approach to parallel repetition
Dinur, I., & Steurer, D. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591884 · Cited by 406
Fast approximate energy minimization with label costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539897 · Cited by 404
Topology control and routing in ad hoc networks: a survey
Rajaraman, R. (2002) · ACM SIGACT News · doi:10.1145/564585.564602 · Cited by 396
Fast Approximate Energy Minimization with Label Costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-011-0437-z · Cited by 381
Beyond independent relevance: methods and evaluation metrics for subtopic retrieval
Zhai, C. X., Cohen, W. W., & Lafferty, J. (2003) · Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval · doi:10.1145/860435.860440 · Cited by 366
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
Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate
Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rincon, D., Sun, X., Wang, Y., Wei, W., & Yuan, Y. (2011) · Proceedings of the 2011 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972818.33 · Cited by 352
Near-optimal Nonmyopic Value of Information in Graphical Models
Krause, A., & Guestrin, C. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1394 · Cited by 349
TimeAware test suite prioritization
Walcott, K. R., Soffa, M. L., Kapfhammer, G. M., & Roos, R. S. (2006) · Proceedings of the 2006 international symposium on Software testing and analysis · doi:10.1145/1146238.1146240 · Cited by 340
Automatic Subspace Clustering of High Dimensional Data
Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (2005) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-005-1396-1 · Cited by 335
Substructure similarity search in graph databases
Yan, X., Yu, P. S., & Han, J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066244 · Cited by 314
Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
Alber, J., Bodlaender, H. L., Fernau, H., Kloks, T., & Niedermeier, R. (2002) · Algorithmica · doi:10.1007/s00453-001-0116-5 · Cited by 304
Streaming submodular maximization: massive data summarization on the fly
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., & Krause, A. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623637 · Cited by 300
Selection of views to materialize in a data warehouse
Gupta, H., & Mumick, I. S. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.16 · Cited by 280
What cannot be computed locally!
Kuhn, F., Moscibroda, T., & Wattenhofer, R. (2004) · Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing · doi:10.1145/1011767.1011811 · Cited by 274
Learning with Submodular Functions: A Convex Optimization Perspective
Bach, F. (2013) · now publishers, Inc. eBooks · doi:10.1561/9781601987570 · Cited by 273
Korte, B., & Vygen, J. (2002) · Algorithms and Combinatorics · doi:10.1007/978-3-662-21711-5_16 · Cited by 273
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Buchbinder, N., & (Seffi) Naor, J. (2009) · now publishers, Inc. eBooks · doi:10.1561/9781601982179 · Cited by 260
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
"Why Should I Trust You?": Explaining the Predictions of Any Classifier
Ribeiro, M. T., Singh, S., & Guestrin, C. (2016) · arXiv
Metadata
- Authors
- Feige, U.
- Venue
- Journal of the ACM
- Published
- 1998-07
- Volume
- 45
- Issue
- 4
- Pages
- 634-652
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2143996311
- Cited by
- 3,086
- References
- 32
- FWCI
- 41.68
- Type
- journal article
- Language
- en
- Open access
- bronze
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.