On the approximation ratio of the 3-Opt algorithm for the (1,2)-TSP

The ( 1 , 2 )-TSP is a special case of the TSP where each edge has cost either 1 or 2. In this paper we give a lower bound of 3 2 for the approximation ratio of the 2-Opt algorithm for the ( 1 , 2 )-TSP . Moreover, we show that the 3-Opt algorithm has an exact approximation ratio of 11 8 for the ( 1 , 2 )-TSP . Furthermore, we introduce the 3-Opt++-algorithm, an improved version of the 3-Opt algorithm for the (1-2)-TSP with an exact approximation ratio of 4 3 .