APPROXIMATE SOLUTION OF NP OPTIMIZATION PROBLEMS

This paper presents the main results obtained in the field of approxim ation algorithms in a unified framework. Most of these results have be en revisited in order to emphasize two basic tools useful for characte rizing approximation classes, that is, combinatorial properties of pro blems and approximation preserving reducibilities. In particular, afte r reviewing the most important combinatorial characterizations of the classes PTAS and FPTAS, we concentrate on the class APX and, as a conc luding result, we show that this class coincides with the class of opt imization problems which are reducible to the maximum satisfiability p roblem with respect to a polynomial-time approximation preserving redu cibility.