Average-case approximation ratio of the 2-opt algorithm for the TSP
From MaRDI portal
Publication:1015301
DOI10.1016/J.ORL.2008.12.002zbMATH Open1159.90494OpenAlexW2057795374MaRDI QIDQ1015301FDOQ1015301
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
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
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
- The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
- 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)
