Worst-Case Analysis of Heuristic Algorithms

The increased focus on heuristics for the approximate solution of integer programs has led to more sophisticated analysis methods for studying their performance. This paper is concerned with the worst-case approach to the analysis of heuristic performance. A worst-case study establishes the maximum deviation from optimality that can occur when a specified heuristic is applied within a given problem class. This is an important piece of information that can be combined with empirical testing and other analyses to provide a more complete evaluation of a heuristic. In this paper the basic ground rules of worst-case analysis of heuristics are reviewed, and a large variety of the existing types of worst-case results are described in terms of the knapsack problem. A selected sample of results for four other problems is given. The paper concludes with a discussion of possibilities for further research.