Bi-criteria path problem with minimum length and maximum survival probability

Nir Halman (), Mikhail Y. Kovalyov (), Alain Quilliot (), Dvir Shabtay () and Moshe Zofi ()
Additional contact information
Nir Halman: Hebrew University of Jerusalem
Mikhail Y. Kovalyov: National Academy of Sciences of Belarus
Alain Quilliot: Université Blaise Pascal, (Clermont-Ferrand II, LIMOS)
Dvir Shabtay: Ben-Gurion University of the Negev
Moshe Zofi: Sapir College

OR Spectrum: Quantitative Approaches in Management, 2019, vol. 41, issue 2, No 5, 469-489

Abstract: Abstract We study a bi-criteria path problem on a directed multigraph with cycles, where each arc is associated with two parameters. The first is the survival probability of moving along the arc, and the second is the length of the arc. We evaluate the quality of a path by two independent criteria. The first is to maximize the survival probability along the entire path, which is the product of the arc probabilities, and the second is to minimize the total path length, which is the sum of the arc lengths. We prove that the problem of finding a path which satisfies two bounds, one for each criterion, is NP-complete, even in the acyclic case. We further develop approximation algorithms for the optimization versions of the studied problem. One algorithm is based on approximate computing of logarithms of arc probabilities, and the other two are fully polynomial time approximation schemes (FPTASes). One FPTAS is based on scaling and rounding of the input, while the other FPTAS is derived via the method of K-approximation sets and functions, introduced by Halman et al. (Math Oper Res 34:674–685, 2009).

Keywords: Shortest path problem; Bi-criteria optimization; Approximation algorithms; Survival probability (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-018-0543-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:orspec:v:41:y:2019:i:2:d:10.1007_s00291-018-0543-1

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-018-0543-1

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().