On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP

DOI10.1016/j.orl.2021.05.012OpenAlexW3169821571MaRDI QIDQ2060589

Xianghui Zhong

Publication date: 13 December 2021

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

Full work available at URL: https://arxiv.org/abs/2103.00504

zbMATH Keywords

approximation algorithmapproximation ratio\((1,2)\)-TSP3-opt algorithm

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Related Items (2)

The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Research on improved ant colony optimization for traveling salesman problem

Cites Work

• Unnamed Item
• 8/7-approximation algorithm for (1,2)-TSP
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• On Syntactic versus Computational Views of Approximability
• Reducibility among Combinatorial Problems
• New Approximation Algorithms for (1,2)-TSP

This page was built for publication: On the approximation ratio of the 3-opt algorithm for the \((1,2)\)-TSP