Combinatorial Problems: Reductibility and Approximation

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.