Approximation Algorithms for NP-Hard Optimization Problems
Philip N. Klein, Neal Young · Chapman & Hall/CRC applied algorithms and data structures series · 2009
Introduction 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 of the objective function at this element is the optimal value. optimal value = minff(x) j x 2 Pg (1) A example of an optimization problem familiar to computer scientists is that of finding a minimum-cost spanning tree of a graph with edge-costs. For this problem, the feasible region P , the set over which we optimize, consists of spanning trees