Fast Approximation Schemes for Multi-Criteria Flow, Knapsack, and Scheduling Problems
Abstract
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would like to find a route that is both short and inexpensive. A solution in this case typically consists of multiple routes because in general, no point is both shortest and cheapest. Finding the efficient frontier or tradeoff curve for such a multi-criteria problem is often difficult, in part because the solution set can have exponentially many points. As a result, multi-criteria problems are often solved by approximating the efficient frontier. A fast approximation scheme (FAS) for a multi-criteria problem is an algorithm that can quickly find an arbitrarily-good approximation to the problem's efficient frontier. Necessary and sufficient conditions for the existence of an FAS for a problem were introduced in [8094]. The conditions are stated in terms of the existence of a V-pseudo-polynomial (VPP) time algorithm for the problem. A new form of reducibility is also introduced and shown to be useful for studying the existence of FAS's. This paper extends the work of [8094] by applying it to a variety of discrete optimization problems. The Source-to-Tree (STT) Network Flow problem is introduced. This problem is interesting because it generalizes many commonly-treated combinatorial optimization problems. A VPP time algorithm is demonstrated for a particular STT problem and is used to show that the problem has an FAS. Results are also derived about the computational complexity of finding approximate solutions to several multi-criteria knapsack, scheduling, and production planning problems. Many theorems extend previously- known results to multi-criteria problems. For some problems, results about problems with binary variables are extended to problems with general integer variables. These and other results are of interest even for problems with only a single criterion.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1995
- Accession Number
- ADA459693
Entities
People
- Hershel M. Safer
- James B. Orlin
Organizations
- Massachusetts Institute of Technology