File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleA QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
Authors
KeywordsDiameter variation
Disjointness
Doubling metrics
Euclidean planes
Geometric objects
Issue Date2010
PublisherSociety for Industrial and Applied Mathematics.
Citation
The ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, TX., 17-19 January 2010. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 256-267 How to Cite?
AbstractWe 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. Copyright © by SIAM.
Persistent Identifierhttp://hdl.handle.net/10722/92627
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorElbassioni, Ken_HK
dc.date.accessioned2010-09-17T10:52:20Z-
dc.date.available2010-09-17T10:52:20Z-
dc.date.issued2010en_HK
dc.identifier.citationThe ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, TX., 17-19 January 2010. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 256-267en_HK
dc.identifier.issn1071-9040-
dc.identifier.urihttp://hdl.handle.net/10722/92627-
dc.description.abstractWe 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. Copyright © by SIAM.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rights© 2010 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms in 2010, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectDiameter variationen_HK
dc.subjectDisjointnessen_HK
dc.subjectDoubling metrics-
dc.subjectEuclidean planes-
dc.subjectGeometric objects-
dc.titleA QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metricsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/1.9781611973075.22-
dc.identifier.scopuseid_2-s2.0-77951672427en_HK
dc.identifier.hkuros170690-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77951672427&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage256en_HK
dc.identifier.epage267en_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridElbassioni, K=8905985900en_HK
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats