Worst-case analysis of two travelling salesman heuristics

DOI10.1016/0167-6377(84)90078-6zbMath0528.90083OpenAlexW2018689801MaRDI QIDQ786657

J. B. Moore, Hoon Liong Ong

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90078-6

zbMATH Keywords

heuristicsworst-case performancecomparison of algorithmssymmetric travelling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)

Related Items (4)

The traveling group problem ⋮ The approximation ratio of the greedy algorithm for the metric traveling salesman problem ⋮ Asymptotic expected performance of some TSP heuristics: An empirical evaluation ⋮ Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• P-Complete Approximation Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Tight bounds for christofides' traveling salesman heuristic
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

This page was built for publication: Worst-case analysis of two travelling salesman heuristics