Random shortest path metrics with applications


Share/Save/Bookmark

Engels, Christian and Manthey, Bodo and Raghavendra Rao, B.V. (2012) Random shortest path metrics with applications. In: Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), 29-31 May 2012, Munich, Germany.

[img]PDF
Restricted to UT campus only
: Request a copy
211Kb
Abstract: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.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/81460
Conference URL:http://ctw2012.informatik.unibw-muenchen.de/
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page