Random shortest path metrics with applications
Christian Engels, Bodo Manthey, B. V. Raghavendra Rao · University of Twente Research Information · 2012
We consider random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. And then the length of an edge is the length of a shortest path with respect to these weights that connects its two endpoints. We prove that the following algorithms achieve an approximation ratio of O(log log n) with high probability in this model: (1) a greedy heuristic for minimum-weight perfect matching, (2) the nearest-neighbor heuristic for the traveling salesman problem (TSP), and (3) any insertion heuristic for the TSP.