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

Christian Engels, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)

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

Keywords

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

Cite this