Worst-Case Analysis of Heuristic Algorithms

Marshall L. Fisher
Additional contact information
Marshall L. Fisher: University of Pennsylvania

Management Science, 1980, vol. 26, issue 1, 1-17

Abstract: 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.

Keywords: programming: integer algorithms; heuristic; computational complexity (search for similar items in EconPapers)
Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.26.1.1 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:26:y:1980:i:1:p:1-17

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().