A Better Approximation Ratio for the Vertex Cover Problem
- 1 January 2005
- book chapter
- Published by Springer Nature
- p. 1043-1050
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems2005
- Expander flows, geometric embeddings and graph partitioning2004
- The importance of being biased2002
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and HypergraphsSIAM Journal on Computing, 2002
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex CoverSIAM Journal on Discrete Mathematics, 1998
- On the LambertW functionAdvances in Computational Mathematics, 1996
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985
- Reducibility among Combinatorial Problems1972