Notes Excerpts:

A large number of (if not, most of) the optimization problems which are required to be solved in practice are NP-hard. Complexity theory tells us that it is impossible to find efficient algorithms for such problems unless P = NP, and this is very unlikely to be true. This does not obviate the need for solving these problems. Observe that NP-hardness only means that, if P <> NP, we cannot find algorithms which will find exactly the optimal solution to all instances of the problem in time which is polynomial in the size of the input. If we relax this rather stringent requirement, it may still be possible to solve the problem reasonably well.

There are three possibilities for relaxing the requirements outlined above to consider a problem well-solved in practice:

- Super-polynomial time heuristics. We may no longer require that the problem be solved in polynomial time. In some cases there are algorithms which are just barely super-polynomial and run reasonably fast in practice.

- Probabilistic analysis of heuristics. Another possibility is to drop the requirement that the solution to a problem cater equally to all input instances. In some applications, it is possible that the class of input instances is severely constrained and for these instances there is an efficient algorithm which will always do the trick.

- Approximation algorithms. Finally, we could relax the requirement that we always find the optimal solution. In practice, it is usually hard to tell the difference between an optimal solution and a near-optimal solution. It seems reasonable to devise algorithms which are really efficient in solving NP-hard problems, at the cost of providing solutions which in all cases is guaranteed to be only slightly sub-optimal

In some situations, the last relaxation of the requirements for solving a problem appears to be the most reasonable. This results in the notion of the "approximate" solution of an optimization problem.

In this book we will attempt to classify as one of three types all hard optimization problems, from the point of view of approximability. Some problems seem to be extremely easy to approximate, e.g. Knapsack, Scheduling and Bin Packing. Other problems are so hard that even finding very poor approximations can be shown to be NP-hard, e.g. Graph Coloring, TSP and Clique. Finally, there is a class of problems which seem to be of intermediate complexity, e.g. Vertex Cover, Euclidean TSP or Steiner Trees. In some cases we will be able to demonstrate that a problem is provably hard to approximate within some error.