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

DOI10.1016/J.ORL.2008.12.002MaRDI QIDQ1015301zbMATH OpenOpenAlexFDO

Authors Christian Engels, Bodo Manthey

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)

Recommendations

• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed analysis of the 2-Opt algorithm for the general TSP

Cites work

• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)

Cited in

(9)

• Probabilistic analysis of optimization problems on sparse random shortest path metrics
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• A partitioning algorithm for minimum weighted Euclidean matching
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1015301)