Premium
A note on detecting unbounded instances of the online shortest path problem
Author(s) -
Boyles Stephen D.,
Rambha Tarun
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21670
Subject(s) - shortest path problem , markov decision process , mathematical optimization , constrained shortest path first , computer science , path (computing) , longest path problem , k shortest path routing , arc (geometry) , mathematics , markov process , theoretical computer science , graph , statistics , geometry , programming language
The online shortest path problem is a type of stochastic shortest path problem in which certain arc costs are revealed en route , and the path is updated accordingly to minimize expected cost. This note addresses the open problem of determining whether a problem instance admits a finite optimal solution in the presence of negative arc costs. We formulate the problem as a Markov decision process and show ways to detect such instances in the course of solving the problem using standard algorithms such as value and policy iteration. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 270–276 2016