Duality theorems in parametric associative optimal path problems

Duality theorems in parametric associative optimal path problems

0.00 Avg rating0 Votes
Article ID: iaor20013562
Country: Singapore
Volume: 17
Issue: 2
Start Page Number: 149
End Page Number: 168
Publication Date: Nov 2000
Journal: Asia-Pacific Journal of Operational Research
Authors:
Keywords: duality
Abstract:

We study optimal (shortest or longest) path problems depending on a parameter in directed networks. In the parametric optimal path problems, path lengths are defined through various associative binary operations: addition, multiplication, fraction and so on. Solving a system of two interrelated functional equations, we simultaneously find both shortest and longest path lengths for all values of the parameter space which is a subset of the real line. Moreover, for every parametric problem (primal problem), we associate another closely related problem (dual problem) where each arc length is the complementary function and path lengths are defined through the associative binary operation which is related to it in the primal problem by DeMorgan's law. The main purpose of this paper is to derive duality theorems between the primal problem and the dual one.

Reviews

Required fields are marked *. Your email address will not be published.