Random shortest path metrics with applications

Christian Engels, Bodo Manthey, B.V. Raghavendra Rao

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

5 Downloads (Pure)


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.
Original languageUndefined
Title of host publicationProceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012)
EditorsA. Brieden, Z.-K. Görgülü, T. Krug, E. Kropat, S. Meyer-Nieberg, G. Mihelcic, S.W. Pickl
Place of PublicationMunich
PublisherUniversität der Bundeswehr München
Number of pages4
ISBN (Print)978-3-943207-05-7
Publication statusPublished - 2012
Event11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012 - Universität der Bundeswehr München, Munich, Germany
Duration: 29 May 201231 May 2012
Conference number: 11

Publication series

PublisherUniversität der Bundeswehr München


Conference11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012
Abbreviated titleCTW
Internet address


  • METIS-289644
  • Average case analysis
  • EWI-21909
  • Approximation algorithms
  • IR-81460

Cite this