ABSTRACT
The local ratio technique has been used to design approximation algorithms for optimization problems since its initiation in the 1980s by Bar-Yehuda and Even. One of the main features of the technique is its simplicity and elegance. A local ratio algorithm is typically intuitive and easy to understand, and its analysis usually reveals the makings of the algorithm, namely it is easy to identify the specific key property or properties of the problem at hand that were instrumental is designing the algorithm. The Local Ratio Lemma applies to minimization (maximization) problems that can be formulated as follows: Given a set of feasibility constraints, a solution vector satisfying the constraints in F is called a feasible solution. The local ratio technique was originally invented as a tool to design approximation algorithms for the Vertex Cover problem. Hence it is only natural to use this problem as a first example. Indeed, present several local ratio 2-approximation algorithm for Vertex Cover.
