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

Arthur Warburton
Additional contact information
Arthur Warburton: University of Ottawa, Ontario, Canada

Operations Research, 1987, vol. 35, issue 1, 70-79

Abstract: 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.

Keywords: 483 multiple-objective shortest paths; 651 approximation of Pareto optima (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.1.70 (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:35:y:1987:i:1:p:70-79

Access Statistics for this article

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