An information-theoretic approach to the robust shortest path problem
David Tschirky · Repository for Publications and Research Data (ETH Zurich) · 2012
The robust shortest path problem is a modified shortest path problem with uncertainty, which arises from variable arc weights. Thereby, each arc of a graph at hand is associated with not only one fixed value but a (potentially infinite) set of values. Hence, a set of costs is assigned to each possible path. The problem then is to solve for a path which is most robust, i.e., which is relatively short as well as stable with respect to its costs. To accomplish this goal, we present a novel information-theoretic ap-proach to compute robust solutions in a weighted graph. As the ba-sis to our method, we always consider a set of two problem instances. Compared to alternative robustness principles, our method avoids over-fitting the data, because it might just be noise. All this is achieved by optimizing an information-theoretic quantity called the ASC mutual information and not a directly cost related function.