16.02.2005

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 boundedmetrics, i.e., metrics where the distances are integers betweenone and some constant upper bound. Recently, Papadimitriou andVempala announced improved approximation hardness results for bothsymmetric and asymmetric TSP with graph metric. In this note, weshow that a similar construction can be used to obtain only slightlyweaker approximation hardness results for TSP with triangleinequality and distances that are integers between one andeight. This shows that the Papadimitriou-Vempala construction is