@Article{BarEve85, author = "R. Bar-Yehuda and S. Even", title = "A local-ratio theorem for approximating the weighted vertex cover problem", journal = "Annals of Discrete Mathematics", year = "1985", volume = "25", pages = "27--46", abstract = "A local-ratio theorem for approximating the weighted vertex cover problem is presented. It consists of reducing the weights of vertices in certain subgraphs and has the effect of local-approximation. Putting together the Nemhauser-Trotter local optimization algorithm and the local-ratio theorem yields several new approximation techniques which improve known results from time complexity, simplicity and performance-ratio point of view. The main approximation algorithm guarantees a ratio of $\displaystyle{2-\frac{1}{\kappa}}$ where $\kappa$ is the smallest integer s.t. $(2 \kappa-1)^{\kappa} \geq n$ (hence: ratio $\displaystyle{\leq 2-\frac{\log \log n}{2 \log n}}$). This is an improvement over the currently known ratios, especially for a ``practical'' number of vertices (e.g. for graphs which have less than $24000, 60000, 10^{12}$ vertices the ratio is bounded by $1.75, 1.8, 1.9$ respectively).", }