Combinatorial Problems: Reductibility and Approximation

Sartaj Sahni and Ellis Horowitz
Additional contact information
Sartaj Sahni: University of Minnesota, Minneapolis, Minnesota
Ellis Horowitz: University of Southern California, Los Angeles, California

Operations Research, 1978, vol. 26, issue 5, 718-759

Abstract: Recent research in the theory of algorithms has determined that many classical operations research problems are computationally related; i.e., an efficient algorithm for one implies the existence of efficient algorithms for everyone or a proof that one is inherently difficult implies they are all so. This paper presents a tutorial of this concept. In contrast to other surveys it does so by selecting a few problems (knapsack, traveling salesperson, multiprocessor scheduling, and flow shop) and carefully shows how they are related. References to most other problems of interest to operations researchers are given. The second part of this paper is a survey on the relatively recent progress in the study of approximation algorithms. These algorithms hold great promise for they work fast and in many cases are guaranteed to work well. Again the techniques for devising and analyzing these algorithms are explained through the continued use of these examples.

Date: 1978
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.5.718 (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:oropre:v:26:y:1978:i:5:p:718-759

Access Statistics for this article

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