Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
TSP with bounded metrics
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
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
Abstract [en]

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.
Keyword [en]
approximation hardness, metric TSP, bounded metric
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-37484DOI: 10.1016/j.jcss.2005.12.001ISI: 000237908400001Scopus ID: 2-s2.0-33646126078OAI: oai:DiVA.org:kth-37484DiVA: diva2:434049
Available from: 2011-08-12 Created: 2011-08-12 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, Lars
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of computer and system sciences (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 42 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf