Random shortest paths: non-euclidean instances for metric optimization problems

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

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 length of an edge is then the length of a shortest path (with respect to the weights drawn) that connects its two endpoints. 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-center 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.
Original languageUndefined
Title of host publicationProceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013)
EditorsK. Chatterjee, J. Sgall
Place of PublicationBerlin
PublisherSpringer
Pages219-230
Number of pages12
ISBN (Print)978-3-642-40312-5
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8087
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • EWI-23415
  • Metric spaces
  • Traveling Salesman Problem
  • Random shortest path
  • IR-87034
  • Approximation algorithms
  • First-passage percolation
  • Heuristics
  • METIS-297687
  • Matching

Cite this