Local Ratio

Authored by: Dror Rawitz

Handbook of Approximation Algorithms and Metaheuristics, Second Edition

Print publication date:  May  2018
Online publication date:  May  2018

Print ISBN: 9781498770118
eBook ISBN: 9781351236423
Adobe ISBN:

10.1201/9781351236423-6

 Download Chapter

 

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.

 Cite
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.