| Article ID: | iaor20082018 |
| Country: | China |
| Volume: | 31 |
| Issue: | 6 |
| Start Page Number: | 801 |
| End Page Number: | 803 |
| Publication Date: | Dec 2005 |
| Journal: | Journal of East China University of Science and Technology |
| Authors: | Liu Jianping |
| Keywords: | heuristics |
The performance ratios of the cheapest insertion method, nearest insertion method and 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.