Reducing curse of dimensionality: Improved PTAS for TSP (with Neighborhoods) in doubling metrics

T. H.Hubert Chant, Shaofeng H.C. Jiang

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

10 Citations (Scopus)

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 given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion of regions was first defined when a QPTAS was given for the problem in [SODA 2010: Chan and Elbassioni]. We combine the techniques in the previous work, together with the recent PTAS for TSP [STOC 2012: Bartal, Gottlieb and Krauthgamer] to achieve a PTAS for TSPN. Moreover, more refined procedures are used to improve the dependence of the running time on the doubling dimension k from the previous exp[O(1)k2] (even for just TSP) to exp[O(1)o(klogk)].

Original languageEnglish
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery (ACM)
Pages754-765
Number of pages12
ISBN (Electronic)9781510819672
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Arlington, United States
Duration: 10 Jan 201612 Jan 2016
Conference number: 27

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CityArlington
Period10/01/201612/01/2016

Fingerprint

Dive into the research topics of 'Reducing curse of dimensionality: Improved PTAS for TSP (with Neighborhoods) in doubling metrics'. Together they form a unique fingerprint.

Cite this