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

Christian Engels, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)


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 languageUndefined
Article number10.1016/j.orl.2008.12.002
Pages (from-to)83-84
Number of pages2
JournalOperations research letters
Issue number2
Publication statusPublished - Mar 2009


  • EWI-16095
  • IR-68061
  • METIS-264041

Cite this