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 | ACM |
| Pages | 754-765 |
| Number of pages | 12 |
| ISBN (Electronic) | 9781510819672 |
| Publication status | Published - 2016 |
| MoE publication type | A4 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/Territory | United States |
| City | Arlington |
| Period | 10/01/2016 → 12/01/2016 |