File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics

TitleReducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
Authors
KeywordsApproximation scheme
Doubling dimension
Metric space
Traveling salesman problem with neighborhoods
Issue Date2018
PublisherAssociation for Computing Machinery, Inc.
Citation
ACM Transactions on Algorithms, 2018, v. 14 n. 1, p. article no. 9 How to Cite?
AbstractWe consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the 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 2010). The regions are partitioned into a constant number of groups, where in each group, regions should have a common upper bound on their diameters and each region designates one point within it such that these points are far away from one another. We combine the techniques in the previous work, together with the recent PTAS for TSP (STOC 2012: Bartal, Gottlieb, and Krauthgamer 2012) to achieve a PTAS for TSPN. However, several nontrivial technical hurdles need to be overcome for applying the PTAS framework to TSPN: (1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. However, for TSPN, it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball. (2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic programming to solve the instance restricted to the sparse ball and recurse on the remaining instance. However, for TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance. Surprisingly, we show that both issues can be resolved by conservatively making the ball in question responsible for all intersecting regions. In particular, a sophisticated charging argument is needed to bound the cost of combining tours in the recursion. 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[2O(k log k)].
Persistent Identifierhttp://hdl.handle.net/10722/290737
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 1.555
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, TH-
dc.contributor.authorJIANG, SHC-
dc.date.accessioned2020-11-02T05:46:24Z-
dc.date.available2020-11-02T05:46:24Z-
dc.date.issued2018-
dc.identifier.citationACM Transactions on Algorithms, 2018, v. 14 n. 1, p. article no. 9-
dc.identifier.issn1549-6325-
dc.identifier.urihttp://hdl.handle.net/10722/290737-
dc.description.abstractWe consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the 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 2010). The regions are partitioned into a constant number of groups, where in each group, regions should have a common upper bound on their diameters and each region designates one point within it such that these points are far away from one another. We combine the techniques in the previous work, together with the recent PTAS for TSP (STOC 2012: Bartal, Gottlieb, and Krauthgamer 2012) to achieve a PTAS for TSPN. However, several nontrivial technical hurdles need to be overcome for applying the PTAS framework to TSPN: (1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. However, for TSPN, it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball. (2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic programming to solve the instance restricted to the sparse ball and recurse on the remaining instance. However, for TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance. Surprisingly, we show that both issues can be resolved by conservatively making the ball in question responsible for all intersecting regions. In particular, a sophisticated charging argument is needed to bound the cost of combining tours in the recursion. 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[2O(k log k)].-
dc.languageeng-
dc.publisherAssociation for Computing Machinery, Inc.-
dc.relation.ispartofACM Transactions on Algorithms-
dc.rightsACM Transactions on Algorithms. Copyright © Association for Computing Machinery, Inc.-
dc.rights©ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn-
dc.subjectApproximation scheme-
dc.subjectDoubling dimension-
dc.subjectMetric space-
dc.subjectTraveling salesman problem with neighborhoods-
dc.titleReducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics-
dc.typeArticle-
dc.identifier.emailChan, TH: hubert@cs.hku.hk-
dc.identifier.authorityChan, TH=rp01312-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/3158232-
dc.identifier.scopuseid_2-s2.0-85042521255-
dc.identifier.hkuros318364-
dc.identifier.volume14-
dc.identifier.issue1-
dc.identifier.spagearticle no. 9-
dc.identifier.epagearticle no. 9-
dc.identifier.isiWOS:000425642700009-
dc.publisher.placeUnited States-
dc.identifier.issnl1549-6325-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats