Stability of Approximation Algorithms and the Knapsack Problem

The investigation of the possibility or the impossibility to efficiently compute approximations of hard optimization problems becomes one of the central and most fruitful areas of current algorithm and complexity theory. Currently, optimization problems are considered to be tractable if there exist randomized polynomial-time approximation algorithms that solve them with a reasonable approximation ratio. Our opinion is that this definition of tractable problems is still too hard. This is because one usually considers the worst-case complexity and what is really important is the complexity of algorithms on “natural” problem instances (real data coming from the practice). Nobody exactly knows what “natural” data are and how to mathematically specify them. But, what one can do is to try to separate the easy problem instances from the hard ones. The aim of this paper is to develop an approach going in this direction.More precisely, a concept for measuring the stability of approximation algorithms is presented. This concept is of theoretical and practical interest because it can be helpful to determine the border between easy problem instances and hard problem instances of complex optimization problems that do not admit polynomial-time approximation algorithms. We illustrate the usefulness of our approach in an exemplary study of the knapsack problem.