ECCC-Report TR04-084https://eccc.weizmann.ac.il/report/2004/084Comments and Revisions published for TR04-084en-usMon, 04 Oct 2004 17:42:23 +0200
Paper TR04-084
| A better approximation ratio for the Vertex Cover problem |
George Karakostas
https://eccc.weizmann.ac.il/report/2004/084We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$
(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,
and by Monien and Speckenmeyer in 1985. The improvement of the vanishing
factor comes as an application of the recent results of Arora, Rao, and Vazirani
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. 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. translates
into the existence of a big independent set.
Mon, 04 Oct 2004 17:42:23 +0200https://eccc.weizmann.ac.il/report/2004/084