Average-case approximation ratio of the 2-opt algorithm for the TSP

Christian Engels; Bodo Manthey

doi:10.1016/j.orl.2008.12.002

Average-case approximation ratio of the 2-opt algorithm for the TSP

Christian Engels
, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

34 Citations (Scopus)

13 Downloads (Pure)

Abstract

We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly $O(\sqrt{n})$ for instances with $n$ nodes, where the edge weights are drawn uniformly and independently at random.

Original language	Undefined
Article number	10.1016/j.orl.2008.12.002
Pages (from-to)	83-84
Number of pages	2
Journal	Operations research letters
Volume	37
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2008.12.002
Publication status	Published - Mar 2009

Keywords

EWI-16095
IR-68061
METIS-264041

Access to Document

10.1016/j.orl.2008.12.002

http://eprints.eemcs.utwente.nl/secure2/16095/01/sdarticle.pdf

Cite this

@article{f93f0380940448088ea7fcd84799f9f8,

title = "Average-case approximation ratio of the 2-opt algorithm for the TSP",

abstract = "We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly \$O(\textbackslash{}sqrt\{n\})\$ for instances with \$n\$ nodes, where the edge weights are drawn uniformly and independently at random.",

keywords = "EWI-16095, IR-68061, METIS-264041",

author = "Christian Engels and Bodo Manthey",

note = "10.1016/j.orl.2008.12.002 ",

year = "2009",

month = mar,

doi = "10.1016/j.orl.2008.12.002",

language = "Undefined",

volume = "37",

pages = "83--84",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Average-case approximation ratio of the 2-opt algorithm for the TSP

AU - Engels, Christian

AU - Manthey, Bodo

N1 - 10.1016/j.orl.2008.12.002

PY - 2009/3

Y1 - 2009/3

N2 - We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly $O(\sqrt{n})$ for instances with $n$ nodes, where the edge weights are drawn uniformly and independently at random.

AB - We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly $O(\sqrt{n})$ for instances with $n$ nodes, where the edge weights are drawn uniformly and independently at random.

KW - EWI-16095

KW - IR-68061

KW - METIS-264041

U2 - 10.1016/j.orl.2008.12.002

DO - 10.1016/j.orl.2008.12.002

M3 - Article

SN - 0167-6377

VL - 37

SP - 83

EP - 84

JO - Operations research letters

JF - Operations research letters

IS - 2

M1 - 10.1016/j.orl.2008.12.002

ER -