A threshold of ln n for approximating set cover
1998/07/01 by Uriel Feige · 3,133 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Cover (algebra) #Discrete mathematics #Greedy algorithm #Mathematics #Order (exchange) #Set (abstract data type) #Set cover problem
paper · pdf · doi:10.1145/285055.285059
published in Journal of the ACM 45(4), 634-652 (Association for Computing Machinery)
openalex publication_date 1998/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
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 .
Citations
Cited by
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Efficient Submodular Function Maximization under Linear Packing Constraints
- Algorithmic Meta-Theorems for Monotone Submodular Maximization
- Almost Optimal Streaming Algorithms for Coverage Problems
- Variable Selection is Hard
- The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
- "Why Should I Trust You?": Explaining the Predictions of Any Classifier
- The Cut and Dominating Set Problem in A Steganographer Network
- Approximation Algorithms for Inventory Problems with Submodular or Routing Costs
- Energy Efficient Scheduling via Partial Shutdown
- Sensor Array Design Through Submodular Optimization
- Fast Semidifferential-based Submodular Function Optimization
- The Unique Games Conjecture with Entangled Provers is False
- Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications
- Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
- Stochastic Conditional Gradient++
- An Information-Theoretic Approach to PMU Placement in Electric Power Systems
- Variational Optimization for the Submodular Maximum Coverage Problem
- Design of Dynamic Algorithms via Primal-Dual Method
- Flexible Representative Democracy: An Introduction with Binary Issues
- Sparse Fault-Tolerant BFS Trees
- Determinantal point processes for machine learning
- Classification by Set Cover: The Prototype Vector Machine
- Approximate k-Cover in Hypergraphs: Efficient Algorithms, and Applications
- Online Learning and Optimization Under a New Linear-Threshold Model with Negative Influence
- Thresholded Covering Algorithms for Robust and Max-Min Optimization
- Improving the betweenness centrality of a node by adding links
- Line Segment Covering of Cells in Arrangements
- Sparse Graphical Memory for Robust Planning
- A Constant-Factor Approximation Algorithm for Point Guarding an Art\n Gallery
- On the Complexity of Edge Packing and Vertex Packing
- Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem
- Capacitated Dominating Set on Planar Graphs
- Hitting Sets Online and Unique-Max Coloring
- Budget Optimization in Search-Based Advertising Auctions
- On the Greedy Algorithm for Combinatorial Auctions with a Random Order
- Complexes Detection in Biological Networks via Diversified Dense Subgraphs Mining
- Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage
- On the Computational Complexities of Three Privacy Measures for Large Networks Under Active Attack
- Fast Non-Monotone Submodular Maximisation Subject to a Matroid Constraint
- On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
- On the Teachability of Randomized Learners
- An Interpretable Model with Globally Consistent Explanations for Credit Risk
- Sparse Solutions to Nonnegative Linear Systems and Applications
- Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
- Node-Constrained Traffic Engineering: Theory and Applications
- Dependent Randomized Rounding for Matroid Polytopes and Applications
- Secluded Connectivity Problems
- A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment
- Stability and Recovery for Independence Systems
- Improved Approximation Algorithms for Geometric Set Cover
- Adaptive Sampling for Fast Constrained Maximization of Submodular Function
- Analytical Approach to Parallel Repetition
- A Reinforcement Learning Approach to the View Planning Problem
- Suggestive Annotation: A Deep Active Learning Framework for Biomedical Image Segmentation
- Resilient Non-Submodular Maximization over Matroid Constraints
- Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions
- On the approximability of robust spanning tree problems
- Efficient Sum-Based Hierarchical Smoothing Under ℓ1-Norm
- FPT-Algorithms for the ℓ-Matchoid Problem with a Coverage Objective
- Diversified Top-k Similarity Search in Large Attributed Networks
- VerIDeep: Verifying Integrity of Deep Neural Networks through Sensitive-Sample Fingerprinting
- Exploiting Coplanar Clusters to Enhance 3D Localization in Wireless\n Sensor Networks
- Optimization with Demand Oracles
- Performance Bounds for the k-Batch Greedy Strategy in Optimization Problems with Curvature
- Behavior-Based online Incentive Mechanism for Crowd Sensing with Budget Constraints
- Online Multi-Facility Location
- Exponential-Time Approximation of Hard Problems
- Guarding Networks Through Heterogeneous Mobile Guards
- Provably Efficient Algorithms for Joint Placement and Allocation of Virtual Network Functions
- A-priori Upper Bounds for the Set Covering Problem
- Deterministic Budget-Feasible Clock Auctions
- Bisimulation-based Approximate Lifted Inference
- Approximation Analysis of Influence Spread in Social Networks
- Parallel Repetition of Free Entangled Games: Simplification and Improvements
- Art Gallery Plus Single Specular-reflection
- Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks
- Approximating low-dimensional coverage problems
- "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
- Algorithms for Constructing Overlay Networks For Live Streaming
- Regularized Non-monotone Submodular Maximization
- Offline and Online Models of Budget Allocation for Maximizing Influence Spread
- Mask-guided sample selection for Semi-Supervised Instance Segmentation
- Combinatorial Blocking Bandits with Stochastic Delays
- Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling
- Coverage Centrality Maximization in Undirected Networks
- On Application of the Local Search and the Genetic Algorithms Techniques to Some Combinatorial Optimization Problems
- Submodular Maximization using Test Scores
- A PTAS for the Weighted Unit Disk Cover Problem
- Approximation Algorithms for Probabilistic Graphs
- Coverage-based Outlier Explanation
- Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
- SABRE: Protecting Bitcoin against Routing Attacks
- On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
- Approximation Algorithms for Dominating Set in Disk Graphs
- Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
- Experimental Design for Non-Parametric Correction of Misspecified Dynamical Models
- Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
- COREATTACK: Breaking Up the Core Structure of Graphs
- New Greedy Heuristics For Set Cover and Set Packing
- Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising
- Resilient Assignment Using Redundant Robots on Transport Networks with Uncertain Travel Time
- Approximating Approximate Distance Oracles
- Online Continuous Submodular Maximization
- Geospatial Optimization Problems
- Differentially Private Online Submodular Optimization
- Minimum Information Dominating Set for Opinion Sampling
- Submodular Hamming Metrics
- On Computing Compression Trees for Data Collection in Sensor Networks
- The covert set-cover problem with application to Network Discovery
- Improved Parameterized Algorithms for Constraint Satisfaction
- Good Graph to Optimize: Cost-Effective, Budget-Aware Bundle Adjustment in Visual SLAM
- Submodular Optimization under Noise
- Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem
- Experimental evaluation of kernelization algorithms to Dominating Set
- Bid Optimization in Broad-Match Ad auctions
- Provenance Views for Module Privacy
- Johnson Coverage Hypothesis: Inapproximability of k-means and k-median\n in Lp metrics
- Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
- Sampling and Representation Complexity of Revenue Maximization
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- Optimized Deployment of Autonomous Drones to Improve User Experience in Cellular Networks
- Interactive Submodular Set Cover
- Efficient and Provable Multi-Query Optimization
- A polynomial lower bound on adaptive complexity of submodular maximization
- A tight analysis of the greedy algorithm for set cover
- Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology
- Sketching and Clustering Metric Measure Spaces
- Optimal approximation for the submodular welfare problem in the value oracle model
- Diversity maximization under matroid constraints
- The Computational Complexity of Truthfulness in Combinatorial Auctions
- Polylogarithmic inapproximability
- On the Parameterized Complexity of Approximating Dominating Set
- Stochastic Submodular Maximization: The Case of Coverage Functions
- Near-optimal Nonmyopic Value of Information in Graphical Models
- Near-linear time approximation schemes for geometric maximum coverage
- One-Round Active Learning
- Unsolved problems in visibility graphs of points, segments, and polygons
- Maximizing Non-monotone Submodular Set Functions Subject to Different\n Constraints: Combined Algorithms
- Implementing data cubes efficiently
- Invitation to Fixed-Parameter Algorithms
- Submodular Function Maximization
- On Multi-Cascade Influence Maximization: Model, Hardness and Algorithmic Framework
- Balanced max 2-sat might not be the hardest
- Polynomial-time approximation schemes for packing and piercing fat objects
- Exploiting Out-of-Domain Data Sources for Dialectal Arabic Statistical Machine Translation
- On the hardness of approximating vertex cover
- Kernelization: Theory of Parameterized Preprocessing
- Algorithmic construction of sets for k -restrictions
- K-Core Maximization through Edge Additions
- Approximability of guarding weak visibility polygons
- Inapproximability Results for Guarding Polygons and Terrains
- Polynomial-time data reduction for dominating set
- Hardness results and approximation algorithms of k-tuple domination in graphs
- On approximability of linear ordering and related NP-optimization problems on graphs
- On the power of unique 2-prover 1-round games
- Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Geometric Dominating Set and Set Cover via Local Search
- Managing aquatic invasions: Optimal locations and operating times for watercraft inspection stations
- Network Construction with Ordered Constraints
- Evaluation of DNF Formulas
- Approximately Certifying the Restricted Isometry Property is Hard
- TimeMachine
- Total domishold graphs: A generalization of threshold graphs, with connections to threshold hypergraphs
- Domination When the Stars Are Out
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
- Seed Selection and Social Coupon Allocation for Redemption Maximization in Online Social Networks
- Greedy algorithm [wikipedia]
- Linear programming relaxation [wikipedia]
- Set cover problem [wikipedia]
- Efficient oligonucleotide probe selection for pan-genomic tiling arrays. [europepmc]
- Optimal selection of epitopes for TXP-immunoaffinity mass spectrometry. [europepmc]
- CLASS: constrained transcript assembly of RNA-seq reads. [europepmc]
- How Many Political Parties Should Brazil Have? A Data-Driven Method to Assess and Reduce Fragmentation in Multi-Party Political Systems. [europepmc]
- An exact algorithm for finding cancer driver somatic genome alterations: the weighted mutually exclusive maximum set cover problem. [europepmc]
- Choosing panels of genomics assays using submodular optimization. [europepmc]
- Automatic identification of optimal marker genes for phenotypic and taxonomic groups of microorganisms. [europepmc]
- Cost-minimizing team hires with participation constraint. [europepmc]
- Capturing sequence diversity in metagenomes with comprehensive and scalable probe design. [europepmc]
- Designing Cost-Sharing Methods for Bayesian Games. [europepmc]
- Connectivity problems on heterogeneous graphs. [europepmc]
- Identification of co-evolving temporal networks. [europepmc]
- Playing games with multiple access channels. [europepmc]
- Deep Compressed Sensing for Learning Submodular Functions. [europepmc]
- A Reinforcement Learning Approach to View Planning for Automated Inspection Tasks. [europepmc]
- Optimized sample selection for cost-efficient long-read population sequencing. [europepmc]
- Ranking with submodular functions on a budget. [europepmc]
- Regularized impurity reduction: accurate decision trees with complexity guarantees. [europepmc]
- Evaluation of combinatorial optimisation algorithms for c-optimal experimental designs with correlated observations. [europepmc]
- Amplidiff: an optimized amplicon sequencing approach to estimating lineage abundances in viral metagenomes. [europepmc]
- On the correlation gap of matroids. [europepmc]
- A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum k -Coverage Problem with Various Genetic Operators. [europepmc]
- The Ground-Set-Cost Budgeted Maximum Coverage Problem. [europepmc]
- Probing transcription factor subsets in gene regulatory networks. [europepmc]
- Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination [europepmc]
Related