A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics

T. H.Hubert Chan, Khaled Elbassioni

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call α-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell [27] and the QPTAS for TSP on doubling metrics by Talwar [30]. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

Original languageBritish English
Title of host publicationProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages256-267
Number of pages12
ISBN (Print)9780898717013
DOIs
StatePublished - 2010
Event21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States
Duration: 17 Jan 201019 Jan 2010

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference21st Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityAustin, TX
Period17/01/1019/01/10

Fingerprint

Dive into the research topics of 'A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics'. Together they form a unique fingerprint.

Cite this