Performance Ratio Analysis of Several Heuristics Algorithm for the TSP

The performance ratios of the cheapest insertion method, nearest insertion method, nearest addition method of traveling salesman problem have been shown to have an upper bound 2, we show the ratios have lower bound approximate to 2. In addition, we prove the performance ratio of the convex hull insertion for the traveling salesman problem in Euclidean plane has the upper bound about a logarithmic function of the number of nodes.