Approximation Algorithms for NP-Hard Optimization Problems

Authored by: Philip N. Klein , Neal E. Young

Algorithms and Theory of Computation Handbook

Print publication date:  November  2009
Online publication date:  November  2009

Print ISBN: 9781584888222
eBook ISBN: 9781584888239
Adobe ISBN:


 Download Chapter



In this chapter, we discuss approximation algorithms for optimization problems. An optimization problem consists in finding the best (cheapest, heaviest, etc.) element in a large set P, called the feasible region and usually specified implicitly, where the quality of elements of the set are evaluated using a function f (x), the objective function, usually something fairly simple. The element that minimizes (or maximizes) this function is said to be an optimal solution and the value of the objective function at this element is the optimal value. 34.1 optimal value   =   min   { f ( x )   |   x ∈   P }

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.