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

This note provides a tight worst case performance analysis of some convex hull insertion heuristics for the Euclidean travelling salesman problem. In particular, starting certain insertion algorithms with the convex hull subtour rather than with a single city subtour degrades worst case performance from twice optimal to three times optimal. By way of contrast, extensive computational experiments suggest that beginning an insertion algorithm with the convex hull subtour may considerably enhance the overall performance of an insertion heuristic.