An Explicit Lower Bound for TSP with Distances One and Two

We show that, for any ϵ>0 , it is NP‐hard to approximate the asymmetric traveling salesman problem with distances one and two within 2805/2804‐ϵ . For the special case where the distance function is constrained to be symmetric, we show a lower bound of 5381/5380‐ϵ , for any ϵ>0 . While it was previously known that there exists some constant, strictly greater than one, such that it is NP‐hard to approximate the traveling salesman problem with distances one and two within that constant, this result is a first step towards the establishment of a good bound. In our proof we develop a new gadget construction to reduce from systems of linear equations mod 2 with two unknowns in each equation and at most three occurrences of each variable. Compared with earlier reductions to the traveling salesman problem with distances one and two, ours reduces the number of cities to less than a tenth of what was previously necessary.