Truly tight bounds for TSP heuristics

DOI10.1016/j.orl.2023.06.003zbMath1525.90360OpenAlexW4381547359MaRDI QIDQ6047697

Cor A. J. Hurkens

Publication date: 12 September 2023

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

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

zbMATH Keywords

worst-case analysismatching boundsTSP-heuristics

Mathematics Subject Classification ID

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

Cites Work

• On the nearest neighbor rule for the metric traveling salesman problem
• On the nearest neighbor rule for the traveling salesman problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Tight bounds for christofides' traveling salesman heuristic
• Lower Bounds for Insertion Methods for TSP
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item