ABSTRACT
Many combinatorial optimization problems are known to be NP-complete† [1-4]. An NP-complete problem can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time. The class of NP-complete problems includes such difficult problems as the traveling salesman, multicommodity network flows, integer programming with bounded variables, set cover, and node cover problems. There is no known polynomial time algorithm for any of these problems. Moreover, mounting empirical evidence (i.e., the identification of more and more NP-complete problems) suggests that it is very likely that no polynomial time algorithms exist for any of these problems. This realization has led many researchers to develop polynomial time approximation algorithms for some NP-complete optimization problems. An approximation algorithm for an optimization problem is generally a heuristic that attempts to obtain a solution whose value is close to the optimal value. For many problems the data themselves are only an estimate. The exact values may be slightly different from these estimates. In such case it is probably just as meaningful to find a solution whose value is close to the optimal value as it is to find an optimal value (as the optimal solution may not remain so once the exact data values are known). For the case of NP-complete problems, the study of approximation algorithms derives an even stronger motivation from the fact that all known optimization algorithms for these problems require an exponential amount of time (measured as a function of problem size) and the expectation that these problems will never be solvable by polynomial time algorithms. Even on the fastest computers, exponential time algorithms are feasible only for relatively small problem sizes. It is better to be able to obtain an approximately optimal solution than no solution at all.
