Approximation algorithms for partial covering problems
- 20 May 2004
- journal article
- Published by Elsevier BV in Journal of Algorithms
- Vol. 53 (1), 55-84
- https://doi.org/10.1016/j.jalgor.2004.04.002
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- An Asymptotic Isoperimetric InequalityGeometric and Functional Analysis, 1998
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex CoverSIAM Journal on Discrete Mathematics, 1998
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- A modified greedy heuristic for the Set Covering problem with improved worst case boundInformation Processing Letters, 1993
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph familiesAlgorithmica, 1992
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- A modification of the greedy algorithm for vertex coverInformation Processing Letters, 1983
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979