A better approximation ratio for the vertex cover problem

✍ Scribed by Karakostas, George

• Book ID: 118266181
• Publisher: Association for Computing Machinery
• Year: 2009
• Tongue: English
• Weight: 88 KB
• Volume: 5
• Category: Article
• ISSN: 1549-6325
• DOI: 10.1145/1597036.1597045

✦ Synopsis

We reduce the approximation factor for the vertex cover to 2 − Θ (1/√log
n
) (instead of the previous 2 − Θ ln ln
n
/2ln
n
obtained by Bar-Yehuda and Even [1985] and Monien and Speckenmeyer [1985]). The improvement of the vanishing factor comes as an application of the recent results of Arora et al. [2004] that improved the approximation factor of the sparsest cut and balanced cut problems. In particular, we use the existence of two big and well-separated sets of nodes in the solution of the semidefinite relaxation for balanced cut, proven by Arora et al. [2004]. We observe that a solution of the semidefinite relaxation for vertex cover, when strengthened with the triangle inequalities, can be transformed into a solution of a balanced cut problem, and therefore the existence of big well-separated sets in the sense of Arora et al. [2004] translates into the existence of a big independent set.