Approximation Schemes for the Restricted Shortest Path Problem

1992/02/01 by Refael Hassin · 1 citation

paper · doi:10.1287/moor.17.1.36

Abstract

This note contains two fully polynomial approximation schemes for the shortest path problem with an additional constraint. The main difficulty in constructing such algorithms arises since no trivial lower and upper bounds on the solution value, whose ratio is polynomially bounded, are known. In spite of this difficulty, one of the algorithms presented here is strongly polynomial. Applications to other problems are also discussed.

Cited by

• SPHERE: Spherical partitioning for large-scale routing optimization

Related

• Improved Approximation Schemes for the Restricted Shortest Path Problem
• Hardness of Approximation for Shortest Path with Vector Costs
• A Polynomial Time Algorithm to Compute an Approximate Weighted Shortest Path
• Approximating the shortest path problem with scenarios
• Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs