A survey of approximately optimal solutions to some covering and packing problems
- 1 June 1997
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 29 (2), 171-209
- https://doi.org/10.1145/254180.254190
Abstract
We survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex covering, the maximum set packing, and maximum independent set problems; we discuss their approximation performance and their complexity. For already known results, any time we have conceived simpler proofs than those already published, we give these proofs, and, for the rest, we cite the simpler published ones. Finally, we discuss how one can relate the approximability behavior (from both a positive and a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems.Keywords
This publication has 43 references indexed in Scilit:
- Average case analysis of greedy algorithms for optimisation problems on set systemsTheoretical Computer Science, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Improved non-approximability resultsPublished by Association for Computing Machinery (ACM) ,1994
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Node-weighted graphs having the König-Egerváry propertyPublished by Springer Science and Business Media LLC ,1984
- On Turán’s theorem for sparse graphsCombinatorica, 1981
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- Khachiyan's linear programming algorithmJournal of Algorithms, 1980
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941