Approximating tsp on metrics with bounded global growth

T. H.Hubert Chan, Anupam Gupta

Research output: Contribution to journalArticlepeer-review

Abstract

The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475-485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for "simpler" instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are "local": the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size vn. Given a metric with global dimension dimC, we give a (1+e)-approximation algorithm that runs in subexponential time, i.e., in exp(O(nde-4dimC ))-time for every constant 0 < d < 1. As mentioned above, metrics with bounded dimC may contain metrics of size O(vn) on which the TSP problem is hard to approximate to within (1 + e). Hence, to do better than a running time of O(exp{vn}), our algorithms find O(1)-approximations to some portions of the tour, and (1 + e)-approximations for other portions, and stitch them together. Moreover, we show that such globally bounded metrics have spanners that preserve distances to arbitrary accuracy and have size T(n1.5).

Original languageEnglish (US)
Pages (from-to)587-617
Number of pages31
JournalSIAM Journal on Computing
Volume41
Issue number3
DOIs
StatePublished - 2012

Keywords

  • Approximation algorithms
  • Global notion of dimension
  • Metric spanners
  • Traveling salesman problem

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Approximating tsp on metrics with bounded global growth'. Together they form a unique fingerprint.

Cite this