## 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 language | English |
---|---|

Title of host publication | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |

Editors | Robert Krauthgamer |

Publisher | Association for Computing Machinery (ACM) |

Pages | 754-765 |

Number of pages | 12 |

ISBN (Electronic) | 9781510819672 |

Publication status | Published - 2016 |

MoE publication type | A4 Article in a conference publication |

Event | ACM-SIAM Symposium on Discrete Algorithms - Arlington, United States Duration: 10 Jan 2016 → 12 Jan 2016 Conference number: 27 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country | United States |

City | Arlington |

Period | 10/01/2016 → 12/01/2016 |