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

DOI10.1016/j.orl.2008.12.002zbMath1159.90494OpenAlexW2057795374MaRDI QIDQ1015301

Bodo Manthey, Christian Engels

Publication date: 7 May 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2008.12.002

zbMATH Keywords

traveling salesman problemaverage-case analysisapproximation ratio2-opt

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems

Cites Work

• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: Average-case approximation ratio of the 2-opt algorithm for the TSP