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

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.