Approximation algorithms have developed in response to the impossibility of solving
a great variety of important optimization problems. Too frequently, when attempting to
get a solution for a problem, one is confronted with the fact that the problem is NP-haid.
This, in the words of Garey and Johnson, means "I can't find an efficient algorithm, but
neither can all these famous people" ([GJ79] p. 3). While this is a significant theoretical
step, it hardly qualifies as a cheering piece of news.
If the optimal solution is unattainable then it is reasonable to sacrifice optimality
and settle for a "good" feasible solution that can be computed efficiently. Of course,
we would like to sacrifice as little optimality as possible, while gaining as much as
possible in efficiency. Trading-off optimality in favor of instability is the paradigm of
The main themes of this book revolve around the design of such algorithms and the
"closeness" to the optimum that is achievable in polynomial time. To evaluate the limits
of approximability. it is important to derive lower bounds or inapproximability results.
In some cases, approximation algorithms must satisfy additional structural requirements
such as being on-line, or working within limited space. This book reviews the design
techniques for such algorithms and the developments in this area since its inception about
three decades ago.