Generalized, Multi-criteria, Shortest path Problems on graphs, Idempotent Semirings, Dualities and the Value of Information

Generalized, Multi-criteria, Shortest path Problems on graphs, Idempotent Semirings, Dualities and the Value of Information

Title : Generalized, Multi-criteria, Shortest path Problems on graphs, Idempotent Semirings, Dualities and the Value of Information
Authors :
Baras, John, S.
Conference : 2011 SIAM Control Conference
Date: July 25 - July 27, 2011

We investigate generalized shortest path problems on graphs with multiple metrics, that are generalized functions of numerical or logical link “weights”. We demonstrate that these problems can be formulated as “linear Optimization or tradeoff problems over partially ordered semirings. We establish conditions for the semirings that guarantee distributed solutions. Considering the information needed for these computations┬áleads to convexity and duality notions, that help quantify the value of information in these distributed optimization problems.

Download Full Paper