A Better Approximation Ratio for the Vertex Cover Problem

We reduce the approximation factor for Vertex Cover to $$2 - \theta(\frac{1}{\sqrt{{\rm log} n}})$$ (instead of the previous $$2- \theta(\frac{{\rm log log} n}{{\rm log}\ n})$$, obtained by Bar-Yehuda and Even [3], and by Monien and Speckenmeyer[11]). The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani [2] 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 in [2]. 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 [2] translates into the existence of a big independent set.