ON THE EXISTENCE OF FAST APPROXIMATION SCHEMES11Supported by Sonderforschungsbereich 21 (DFG), Institut für Operations Research, Universität Bonn.

We characterize those combinatorial optimization problems which can be solved approximately by polynomially bounded algorithms. Using slight modifications of the Sahni and Ibarra and Kim algorithms for the knapsack problem we prove that there is no fast approximation scheme unless their algorithmic ideas apply. Hence we show that these algorithms are not only the origin but also prototypes for all polynomial or fully polynomial approximation schemes.