A threshold of ln n for approximating set cover (preliminary version)
Explore this paper's citation graph
Summary
It is proved that (1 - o(1) ln n setcover is a threshold below which setcover cannot be approximated efficiently, unless NP has slightlysuperpolynomial time algorithms.
- Type
- article
- Published
- 1996-07-01
- Cited by
- 3,062
- References
- 45
- Access
- Open access
- OpenAlex
- https://openalex.org/W2000869424
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:52827488
Keywords
Cover (algebra), Set (abstract data type), Computer science, Set cover problem, Engineering
References
- Approximating the Minimum Maximal Independence Number
- Two-prover one-round proof systems: their power and their problems (extended abstract)
- A tight analysis of the greedy algorithm for set cover
- The Knowledge Complexity of Interactive Proof Systems
- Easy and hard bottleneck location problems
- Approximation Algorithms for NP-Hard Problems
- A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
- A parallel repetition theorem
- A simple heuristic for the p-centre problem
- On the Power of Multi-Prover Interactive Protocols
- Probabilistic checking of proofs: a new characterization of NP
- Optimization, Approximation, and Complexity Classes
- Approximation algorithms for combinatorial problems
- Non Deterministic Polynomial Optimization Problems and their Approximations
- On the hardness of approximating minimization problems
- A Best Possible Heuristic for the k-Center Problem
- Multi-prover interactive proofs: how to remove intractability assumptions
- Algebraic methods for interactive proof systems
- Improved approximations of packing and covering problems
- Interactive proofs and the hardness of approximating cliques
Cited by
- Computational study for domination problems in planar graphs
- A Theoretical Analysis of Query Selection for Collaborative Filtering
- A Note on Set Cover Inapproximability Independent of Universe Size
- Algorithms for distributed monitoring in multi-channel ad hoc wireless networks
- Heuristic algorithms for wireless mesh network planning
- The Submodular Welfare Problem with Demand Queries
- Learning Coverage Functions
- Improvements on Seeding Based Protein Sequence Similarity Search
- A lower bound for approximating the grundy number
- Fast Multi-stage Submodular Maximization
- Approximation Algorithms for Constrained Knapsack Problems
- Querying Uncertain Data in Resource Constrained Settings
- On Routing, Backbone Formation and Barrier Coverage in Wireless Ad Hoc and Sensor Networks
- Approximation algorithms to the network design problems
- The complex of sensor placement in municipal water networks.
- On Approximating Four Covering/Packing Problems With Applications to Bioinformatics
- Factored Planning
- On Vulnerability of Banking Networks
- Online Learning Techniques for Improving Robot Navigation in Unfamiliar Domains
- NFA reduction via hypergraph vertex cover approximation
Related papers
- Using DataGrid Control to Realize DataBase of Querying in VB6.0
- Study and Two Types of Typical Usage of DataGrid Web Server Control
- An Efficient Algorithm for Finding an Irredundant Set Cover
- Cover Set Problem in Directional Sensor Networks
- Optimized location of light sources to cover a rectangular region
- Improved n 1-cover discovery using perimeter coverage information
- The Set-Partitioning Problem: Set Covering with Equality Constraints
- Solving the set cover problem on a supercomputer