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

Mohsen Abdolhosseinzadeh

International Journal of Operational Research, 2022, vol. 43, issue 1/2, 119-130

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. (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=121483 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:43:y:2022:i:1/2:p:119-130

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().