File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: 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
KeywordsDoubling metrics
Quasi-polynomial time approximation scheme
Traveling salesman problem with neighborhoods
Issue Date2011
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm
Citation
Discrete And Computational Geometry, 2011, v. 46 n. 4, p. 704-723 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 quasi-polynomial time approximation scheme (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 polynomial time approximation scheme (PTAS) for TSPN on the Euclidean plane by Mitchell (in SODA, pp. 11-18, 2007) and the QPTAS for TSP on doubling metrics by Talwar (in 36th STOC, pp. 281-290, 2004). 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. © 2011 The Author(s).
Persistent Identifierhttp://hdl.handle.net/10722/144883
ISSN
2015 Impact Factor: 0.816
2015 SCImago Journal Rankings: 1.278
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorElbassioni, Ken_HK
dc.date.accessioned2012-02-21T05:43:58Z-
dc.date.available2012-02-21T05:43:58Z-
dc.date.issued2011en_HK
dc.identifier.citationDiscrete And Computational Geometry, 2011, v. 46 n. 4, p. 704-723en_HK
dc.identifier.issn0179-5376en_HK
dc.identifier.urihttp://hdl.handle.net/10722/144883-
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 quasi-polynomial time approximation scheme (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 polynomial time approximation scheme (PTAS) for TSPN on the Euclidean plane by Mitchell (in SODA, pp. 11-18, 2007) and the QPTAS for TSP on doubling metrics by Talwar (in 36th STOC, pp. 281-290, 2004). 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. © 2011 The Author(s).en_HK
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htmen_HK
dc.relation.ispartofDiscrete and Computational Geometryen_HK
dc.rightsThe Author(s)en_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong Licenseen_US
dc.subjectDoubling metricsen_HK
dc.subjectQuasi-polynomial time approximation schemeen_HK
dc.subjectTraveling salesman problem with neighborhoodsen_HK
dc.titleA QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metricsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4551/resserv?sid=springerlink&genre=article&atitle=A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics&title=Discrete & Computational Geometry&issn=01795376&date=2011-12-01&volume=46&issue=4& spage=704&authors=T.-H. Hubert Chan, Khaled Elbassionien_US
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1007/s00454-011-9337-9en_HK
dc.identifier.scopuseid_2-s2.0-80053633054en_HK
dc.identifier.hkuros188722-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80053633054&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume46en_HK
dc.identifier.issue4en_HK
dc.identifier.spage704en_HK
dc.identifier.epage723en_HK
dc.identifier.eissn1432-0444en_US
dc.identifier.isiWOS:000295680100005-
dc.publisher.placeUnited Statesen_HK
dc.description.otherSpringer Open Choice, 21 Feb 2012en_US
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridElbassioni, K=8905985900en_HK
dc.identifier.citeulike9049957-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats