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: | Hassin Refael |
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.