@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).",
}