Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems

We study methods for approximating the set of Pareto optimal paths in multiple-objective, shortest-path problems. Known generalizations of standard shortest-path methods will compute this set, but can suffer from rapidly increasing computational and storage demands as problem size increases. In an effort to avoid such difficulties, we develop approximation methods that can estimate the Pareto optima to any required degree of accuracy. The approximation methods are “fully polynomial”; that is, they operate in time and space bounded by a polynomial in problem size and accuracy of approximation—the greater the accuracy, the more time required to reach a solution. We show how approximation methods may be applied to yield fully polynomial approximation schemes for a variety of NP-complete, single-objective problems.