Random shortest path metrics with applications

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

Random shortest path metrics with applications

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

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 language	Undefined
Title of host publication	Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012)
Editors	A. Brieden, Z.-K. Görgülü, T. Krug, E. Kropat, S. Meyer-Nieberg, G. Mihelcic, S.W. Pickl
Place of Publication	Munich
Publisher	Universität der Bundeswehr München
Pages	121-124
Number of pages	4
ISBN (Print)	978-3-943207-05-7
Publication status	Published - 2012
Event	11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012 - Universität der Bundeswehr München, Munich, Germany Duration: 29 May 2012 → 31 May 2012 Conference number: 11 http://or.w3.rz.unibw-muenchen.de/ctw2012/

Publication series

Name
Publisher	Universität der Bundeswehr München

Conference

Conference	11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012
Abbreviated title	CTW
Country/Territory	Germany
City	Munich
Period	29/05/12 → 31/05/12
Internet address	http://or.w3.rz.unibw-muenchen.de/ctw2012/

Keywords

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

Access to Document

http://eprints.eemcs.utwente.nl/secure2/21909/01/CTW2012.pdf

Cite this

Engels, C., Manthey, B., & Raghavendra Rao, B. V. (2012). Random shortest path metrics with applications. In A. Brieden, Z-K. Görgülü, T. Krug, E. Kropat, S. Meyer-Nieberg, G. Mihelcic, & S. W. Pickl (Eds.), Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012) (pp. 121-124). Universität der Bundeswehr München. http://eprints.eemcs.utwente.nl/secure2/21909/01/CTW2012.pdf

Engels, Christian ; Manthey, Bodo ; Raghavendra Rao, B.V. / Random shortest path metrics with applications. Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012). editor / A. Brieden ; Z.-K. Görgülü ; T. Krug ; E. Kropat ; S. Meyer-Nieberg ; G. Mihelcic ; S.W. Pickl. Munich : Universität der Bundeswehr München, 2012. pp. 121-124

@inproceedings{88da4df1553d4058b376daa17dde4f68,

title = "Random shortest path metrics with applications",

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.",

keywords = "METIS-289644, Average case analysis, EWI-21909, Approximation algorithms, IR-81460",

author = "Christian Engels and Bodo Manthey and {Raghavendra Rao}, B.V.",

note = "http://ctw2012.informatik.unibw-muenchen.de/; null ; Conference date: 29-05-2012 Through 31-05-2012",

year = "2012",

language = "Undefined",

isbn = "978-3-943207-05-7",

publisher = "Universit{\"a}t der Bundeswehr M{\"u}nchen",

pages = "121--124",

editor = "A. Brieden and Z.-K. G{\"o}rg{\"u}l{\"u} and T. Krug and E. Kropat and S. Meyer-Nieberg and G. Mihelcic and S.W. Pickl",

booktitle = "Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012)",

url = "http://or.w3.rz.unibw-muenchen.de/ctw2012/",

}

Engels, C, Manthey, B & Raghavendra Rao, BV 2012, Random shortest path metrics with applications. in A Brieden, Z-K Görgülü, T Krug, E Kropat, S Meyer-Nieberg, G Mihelcic & SW Pickl (eds), Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012). Universität der Bundeswehr München, Munich, pp. 121-124, 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2012, Munich, Germany, 29/05/12. <http://eprints.eemcs.utwente.nl/secure2/21909/01/CTW2012.pdf>

Random shortest path metrics with applications. / Engels, Christian; Manthey, Bodo; Raghavendra Rao, B.V.

Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012). ed. / A. Brieden; Z.-K. Görgülü; T. Krug; E. Kropat; S. Meyer-Nieberg; G. Mihelcic; S.W. Pickl. Munich : Universität der Bundeswehr München, 2012. p. 121-124.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Random shortest path metrics with applications

AU - Engels, Christian

AU - Manthey, Bodo

AU - Raghavendra Rao, B.V.

N1 - Conference code: 11

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - METIS-289644

KW - Average case analysis

KW - EWI-21909

KW - Approximation algorithms

KW - IR-81460

M3 - Conference contribution

SN - 978-3-943207-05-7

SP - 121

EP - 124

BT - Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012)

A2 - Brieden, A.

A2 - Görgülü, Z.-K.

A2 - Krug, T.

A2 - Kropat, E.

A2 - Meyer-Nieberg, S.

A2 - Mihelcic, G.

A2 - Pickl, S.W.

PB - Universität der Bundeswehr München

CY - Munich

Y2 - 29 May 2012 through 31 May 2012

ER -