09.02.2006

The general asymmetric TSP with triangle inequality is known to beapproximable only within logarithmic factors. In this paper we studythe asymmetric and symmetric TSP problems with bounded metrics,i.e., metrics where the distances are integers betweenone and some constant upper bound. In this case, the problem isknown to be approximable within a constant factor. We prove that itis NP-hard to approximate the asymmetric TSP with distances one andtwo within 321/320 - ε and that it is NP-hard toapproximate the symmetric TSP with distances one and two within741/740 - ε for every constant ε > 0.
Recently, Papadimitriou and Vempala announced improved approximationhardness results for both symmetric and asymmetric TSP with graph metric.We show that a similar construction can be used to obtain only slightlyweaker approximation hardness results for TSP with triangle inequality anddistances that are integers between one and eight. This shows that thePapadimitriou-Vempala construction is