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 [1]. 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. Initially, the simplicity of the technique leads to believe that it has very limited use. However, over the years it has evolved into a powerful technique with broad applicability.
