Accession Number:

ADA459693

Title:

Fast Approximation Schemes for Multi-Criteria Flow, Knapsack, and Scheduling Problems

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE

Personal Author(s):

Report Date:

1995-01-01

Pagination or Media Count:

52.0

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 problems 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 FASs. 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.

Subject Categories:

  • Computer Programming and Software
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE