TSP with bounded metrics
2006 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 72, no 4, 509-546 p.Article in journal (Refereed) Published
The general asymmetric TSP with triangle inequality is known to be approximable only within logarithmic factors. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics, i.e., metrics where the distances are integers between one and some constant upper bound. In this case, the problem is known to be approximable within a constant factor. We prove that it is NP-hard to approximate the asymmetric TSP with distances one and two within 321/320 - epsilon and that it is NP-hard to approximate the symmetric TSP with distances one and two within 741/740 - epsilon for every constant epsilon > 0. Recently, Papadimitriou and Vempala announced improved approximation hardness results for both symmetric and asymmetric TSP with graph metric. We show that a similar construction can be used to obtain only slightly weaker approximation hardness results for TSP with triangle inequality and distances that are integers between one and eight. This shows that the Papadimitriou-Vempala construction is "local" in nature and, intuitively, indicates that it cannot be used to obtain hardness factors that grow with the size of the instance.
Place, publisher, year, edition, pages
2006. Vol. 72, no 4, 509-546 p.
approximation hardness, metric TSP, bounded metric
IdentifiersURN: urn:nbn:se:kth:diva-37484DOI: 10.1016/j.jcss.2005.12.001ISI: 000237908400001ScopusID: 2-s2.0-33646126078OAI: oai:DiVA.org:kth-37484DiVA: diva2:434049