Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BALANCED CUT:
Reports tagged with balanced cut:
TR04-084 | 28th September 2004
George Karakostas

#### A better approximation ratio for the Vertex Cover problem

We 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 ... more >>>

ISSN 1433-8092 | Imprint