Performance Ratio Analysis of the Convex Hull Method for the Euclidean Traveling Salesman Problem

In this paper, we show the performance ratio of the convex hull method for the Euclidean traveling salesman problem has the upper bound n/2. Meanwhile, we give an algorithm that its performance ratio has lower bound approximate to n/2. In addition, we prove the performance ratios of the convex hull cheapest insertion method, convex hull nearest insertion method and convex hull nearest addition method for the Euclidean traveling salesman problem have the upper bound 3.