Basic Methodologies and Applications

Authored by: Teofilo F. Gonzalez

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-2

 Download Chapter

 

Abstract

In Chapter 1, we present an overview of approximation algorithms and metaheuristics as well as an overview for both volumes of this handbook. In this chapter, we discuss in more detail the basic methodologies and apply them to classic problems. These methodologies include the four major ones: restriction (algorithmic and structural), relaxation (numerical and structural), rounding, and transformation. Greedy methods fall in the class of restriction methods (structural), linear programming (LP)-rounding fall under relaxation (numerical) and α -vectors, local ratio and primal-dual fall under problem transformation. We also discuss in more detail inapproximability and show that the “original” version of the traveling salesperson problem (TSP) is constant ratio inapproximable.

 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.