hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Probabilistic analysis for metric optimization problems has mostly been
conducted on random Euclidean instances, but little is known about metric
instances drawn from distributions other than the Euclidean. This motivates our
study of random metric instances for optimization problems obtained as follows:
Every edge of a complete graph gets a weight drawn independently at random. The
distance between two nodes is then the length of a shortest path (with respect
to the weights drawn) that connects these nodes.
We prove structural properties of the random shortest path metrics generated
in this way. Our main structural contribution is the construction of a good
clustering. Then we apply these findings to analyze the approximation ratios of
heuristics for matching, the traveling salesman problem (TSP), and the k-median
problem, as well as the running-time of the 2-opt heuristic for the TSP. The
bounds that we obtain are considerably better than the respective worst-case
bounds. This suggests that random shortest path metrics are easy instances,
similar to random Euclidean instances, albeit for completely different
structural reasons.
