Approximation Algorithms for the Set Covering and Vertex Cover Problems

1982/08/01 by Dorit S. Hochbaum · 508 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Cover (algebra) #Covering problems #Edge cover #Engineering #Feedback vertex set #Graph #Heuristic #Mathematical optimization #Mathematics #Set (abstract data type) #Set cover problem #Statistics #Value (mathematics) #Vertex (graph theory) #Vertex cover

paper · doi:10.1137/0211045

published in SIAM Journal on Computing 11(3), 555-556 (Society for Industrial and Applied Mathematics)

openalex publication_date 1982/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We propose a heuristic that delivers in O(n³ ) steps a solution for the set covering problem the value of which does not exceed the maximum number of sets covering an element times the optimal value.

Citations

• Approximation algorithms for combinatorial problems
• Paths, Trees, and Flowers

Cited by

• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
• Capacitated Partition Vertex Cover and Partition Edge Cover
• An Approximate, Efficient Solver for LP Rounding
• A Graph-Theoretical Perspective on Law Design for Multiagent Systems
• Minimum Vertex Cover in Rectangle Graphs
• On the monotonization of the training set
• A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming
• Differentially Private Combinatorial Optimization
• The Online Submodular Cover Problem
• Minimum Sensor Placement for Robust Observability of Structured Complex Networks
• Weighted Partition Vertex and Edge Cover
• A Survey of Skyline Query Processing
• Iteratively reweighted greedy set cover
• Primal-Dual Neural Algorithmic Reasoning
• Reference Point Methods and Approximation in Multicriteria Optimization
• Capacitated Domination: Constant Factor Approximation for Planar Graphs
• Brain size bias compensated graph-theoretical parameters are also better in women’s structural connectomes
• Graph Theoretical Analysis Reveals: Women’s Brains Are Better Connected than Men’s
• Network flow and 2-satisfiability
• Almost optimal set covers in finite VC-dimension
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Evaluation of DNF Formulas

Related

• A Near Optimal Approximation Algorithm for Vertex-Cover Problem
• Improved Greedy Algorithm for Set Covering Problem
• A (1.999999)-approximation ratio for vertex cover problem
• A polynomial time \frac 3 2 -approximation algorithm for the vertex cover problem on a class of graphs
• On the Set Multi-Cover Problem in Geometric Settings