A problem of finding a path between two vertices of a directed multigraph is studied. Each arc is associated with two numbers which can be viewed as the survival probabilty and the length, respectively. The quality of a path is evaluated by two functions, one of which is the product of the arc probabilities and the other is the sum of the arc lenths. We prove NP-completeness of the decision version of this problem, in which there is a lower bound on the multiplicative function and an upper bound on the additive function. We also develop approximation algorithms for the optimization versions of the studied problem, and evaluate their worst case performances. One algorithm is based on approximate computing of logarithms of the arc probabilities, and another is a fully polynomial time approximation scheme (FPTAS).
| Subject : | : | Abstracts |
| Topics | : | Multi-objective VRPs |
| PDF version | : |  PDF version |
