Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem

DOI10.1016/0167-6377(93)90082-RMaRDI QIDQ2367039zbMATH OpenFDO

Authors A. R. Warburton

Publication date 16 August 1993

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

Full work available at URL https://doi.org/10.1016/0167-6377(93)90082-R

zbMATH Keywords

convex hull insertion heuristicsEuclidean travelling salesmaninsertion algorithmstight worst case performance analysisworst-case analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Worst-case analysis of a new heuristic for the travelling salesman problem
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• scientific article; zbMATH DE number 3950233
• The convex-hull-and-line traveling salesman problem: A solvable case

Cites work

• An Analysis of Several Heuristics for the Traveling Salesman Problem
• scientific article; zbMATH DE number 3918121 (Why is no real title available?)
• scientific article; zbMATH DE number 3950233 (Why is no real title available?)
• scientific article; zbMATH DE number 3799403 (Why is no real title available?)
• Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem

Cited in

(6)

• Quantizers ad the worst case Euclidean traveling salesman problem
• Novel concave hull-based heuristic algorithm for TSP
• Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
• scientific article; zbMATH DE number 4199979 (Why is no real title available?)
• WORST-CASE ANALYSIS FOR PLANAR MATCHING AND TOUR HEURISTICS WITH BUCKETING TECHNIQUES AND SPACEFILLING CURVES
• Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems

This page was built for publication: Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem

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