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

Share/Save/Bookmark

Engels, Christian and Manthey, Bodo (2009) Average-case approximation ratio of the 2-opt algorithm for the TSP. Operations Research Letters, 37 (2). pp. 83-84. ISSN 0167-6377

[img] PDF
Restricted to UT campus only
: Request a copy
484kB
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.

Item Type:Article
Copyright:© 2009 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/68061
Official URL:http://dx.doi.org/10.1016/j.orl.2008.12.002
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page