Approximation Algorithms for the Set Covering and Vertex Cover Problems

1982/08/01 by Dorit S. Hochbaum · 13 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Advanced Graph Theory Research

paper · doi:10.1137/0211045

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\n 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

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