@Article{Bar98a,
  author  =   "R. Bar-Yehuda",
  title =     "One for the Price of Two: A Unified  Approach
                for  Approximating Covering Problems
               ",
  journal =      "To apear in ALGORITHMICA",
  year =         "1998",
  abstract =     "
We present a simple and unified approach for developing and analyzing
approximation algorithms for covering problems. We illustrate this on
approximation algorithms for the following problems: Vertex Cover, Set
Cover, Feedback Vertex Set, Generalized Steiner Forest and related
problems.

The main idea can be phrased as follows: iteratively, pay two dollars
(at most) to reduce the total optimum by one dollar (at least), so the
rate of payment is no more than twice the rate of the optimum
reduction. This implies a total payment (i.e., approximation cost)
$\leq$ twice the optimum cost.

Our main contribution is based on a formal definition for covering
problems, which includes all the above fundamental problems and
others. We further extend the Bafna, Berman and Fujito extension of
the Local-Ratio theorem. Our extension eventually yields a short
generic $r$-approximation algorithm which can generate most known
approximation algorithms for most covering problems.

Another extension of the Local-Ratio theorem to randomized algorithms
gives a simple proof of Pitt's randomized approximation for Vertex
Cover. Using this approach, we develop a modified greedy algorithm,
which for Vertex Cover, gives an expected performance ratio $ \leq 2$.
\end{abstract}

\noindent{\bf Keywords:}
Approximation Algorithm, Local Ratio, Primal-Dual, Covering Problems,
Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner
Forest, Randomized Approximations.
      ",
  }