A note on detecting unbounded instances of the online shortest path problem

A note on detecting unbounded instances of the online shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor20162576
Volume: 67
Issue: 4
Start Page Number: 270
End Page Number: 276
Publication Date: Jul 2016
Journal: Networks
Authors: ,
Keywords: combinatorial optimization, stochastic processes, programming: markov decision
Abstract:

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.

Reviews

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