Title: A lower bound competitive ratio for the online stochastic shortest path problem

Authors: Mohsen Abdolhosseinzadeh

Addresses: Department of Mathematics, University of Bonab, Bonab, Iran

Abstract: In online networks, some parameters are not initially known by decision-makers, especially arc costs that are revealed over time, thereby online decisions are made without complete knowledge of the future events. Three kinds of statistical information are available in terms of online manner arrival of the last traversed nodes: the exact traversed length, the average shortest path length and the shortest path length. Three different stochastic models are considered and the related stochastic online decision criteria are obtained, such that the best competitive ratio is 2.3130. Under the assumption that the online decision-maker is informed about the intervals of the arc costs, and after some constant competitive ratios are produced, 2.3130 is determined as the best obtained lower bound competitive ratio against some previous works.

Keywords: online stochastic network; online decision problem; competitive analysis; online stochastic shortest path; O-SSP.

DOI: 10.1504/IJOR.2022.121483

International Journal of Operational Research, 2022 Vol.43 No.1/2, pp.119 - 130

Received: 13 Oct 2019
Accepted: 07 Apr 2020
Published online: 16 Mar 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article