Treffer: approximation results for the Traveling Salesman and related Problems

This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and can not be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm idea improves this ratio to 3/4 and we obtain a differential non-approximation threshold equal to 741/742. Remark that the 3/4-differential approximation result have been recently proved by a way more specific to the 1,2-case and with another algorithm in the recent conference (symposia on Fundamentals of Computation Theory 2001). Based upon these results, we establish new bounds for standard ratio: 5/6 for Max TSP[a,2a] and 7/8 for Max TSP[1,2]. We also derive some approximation results on partition graph problems by paths.