The minimum traveling salesman problem with distances one and two is the following problem: Given a complete undirected graph G = (V, E) with a cost function w : E → {1,2}, find a Hamiltonian tour of minimum cost. In this paper, we provide an approximation algorithm for this problem achieving a performance guarantee of (315)/(271). This algorithm can be further improved obtaining a performance guarantee of (65)/(56). This is better than the one achieved by Papadim-itriou and Yannakakis, with a ratio 7/6, more than a decade ago. We enhance their algorithm by an involved procedure and find an improved lower bound for the cost of an optimal Hamiltonian tour.
展开▼
