10.1.2005

The general asymmetric TSP with triangle inequality is known to be approximableonly within logarithmic factors. In this paper we study the asymmetricand symmetric TSP problems with bounded metrics, i.e., metrics where the distancesare integers between one and some constant upper bound. In this case, the problemis known to be approximable within a constant factor. We prove that it is NP-hardto approximate the asymmetric TSP with distances one and two within 321/320-εand that it is NP-hard to approximate the symmetric TSP with distances one and twowithin 741/740-ε for every constant ε > 0.