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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom