IDEAS home Printed from https://ideas.repec.org/a/ids/ijores/v43y2022i1-2p119-130.html
   My bibliography  Save this article

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

Author

Listed:
  • Mohsen Abdolhosseinzadeh

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.

Suggested Citation

  • Mohsen Abdolhosseinzadeh, 2022. "A lower bound competitive ratio for the online stochastic shortest path problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 43(1/2), pages 119-130.
    • Handle: RePEc:ids:ijores:v:43:y:2022:i:1/2:p:119-130
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=121483
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:ijores:v:43:y:2022:i:1/2:p:119-130. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=170 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.