A better approximation ratio for the ver
β
Karakostas, George
π
Article
π
2009
π
Association for Computing Machinery
π
English
β 88 KB
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