Stefan Klootwijk (University of Twente)

On Random Shortest Path Metrics

Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, “beyond worst-case analysis” of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions.

In this talk we take a look at another class of metric spaces, namely random shortest path metrics. A random shortest path metric is constructed by drawing independent random edge weights for each edge in a given graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. This model is also known as first passage percolation. We derive some properties of such metrics, and look at the performance of some simple heuristics for the minimum distance perfect matching problem, the traveling salesman problem, and the k-median problem on instances obtained from such metrics.

http://www.win.tue.nl/StoSem/