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

Christian Engels, Bodo Manthey

22 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 language Undefined 10.1016/j.orl.2008.12.002 83-84 2 Operations research letters 37 2 https://doi.org/10.1016/j.orl.2008.12.002 Published - Mar 2009

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