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)

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.
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
Pages121-124
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
http://or.w3.rz.unibw-muenchen.de/ctw2012/

Publication series

Name
PublisherUniversität der Bundeswehr München

Conference

Conference11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012
Abbreviated titleCTW
Country/TerritoryGermany
CityMunich
Period29/05/1231/05/12
Internet address

Keywords

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

Cite this