Path Problems with Additive and Multiplicative Objectives
Mikhail Kovalyov  1@  , Alain Quilliot  2@  , Dvir Shabtay  3@  , Moshe Zofi  4@  
1 : United Institute of Informatics Problems  (UIIP [Minsk])  -  Website
6, Surganova str, 220012 Minsk, Republic of Belarus -  Belarus
2 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Institut Français de Mécanique Avancée, Université Blaise Pascal - Clermont-Ferrand II, Université d'Auvergne - Clermont-Ferrand I, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France
3 : Ben-Gurion University of Negev
4 : Sapir Collage  (Sapir Collage)

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).


Online user: 1 RSS Feed