Approximation schemes for the restricted shortest path problem

Approximation schemes for the restricted shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor19921476
Country: United States
Volume: 17
Issue: 1
Start Page Number: 36
End Page Number: 42
Publication Date: Feb 1992
Journal: Mathematics of Operations Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.