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.