The Traveling Salesman Problem with Distances One and Two
Christos H. Papadimitriou, Mihalis Yannakakis · Mathematics of Operations Research · 1993
We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.