File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

TitleA Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
Authors
KeywordsDoubling dimension
polynomial time approximation scheme
prize collecting
Steiner tree problem
traveling salesman problem
Issue Date2020
PublisherAssociation for Computing Machinery, Inc.
Citation
ACM Transactions on Algorithms, 2020, v. 16 n. 2, p. article no. 24 How to Cite?
AbstractWe present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be a tree for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. Our unified PTAS is based on the previous dynamic programming frameworks proposed in Talwar (STOC 2004) and Bartal, Gottlieb, Krauthgamer (STOC 2012). However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we need to develop new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions.
Persistent Identifierhttp://hdl.handle.net/10722/290738
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, H-
dc.contributor.authorJIANG, SHC-
dc.date.accessioned2020-11-02T05:46:25Z-
dc.date.available2020-11-02T05:46:25Z-
dc.date.issued2020-
dc.identifier.citationACM Transactions on Algorithms, 2020, v. 16 n. 2, p. article no. 24-
dc.identifier.issn1549-6325-
dc.identifier.urihttp://hdl.handle.net/10722/290738-
dc.description.abstractWe present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be a tree for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. Our unified PTAS is based on the previous dynamic programming frameworks proposed in Talwar (STOC 2004) and Bartal, Gottlieb, Krauthgamer (STOC 2012). However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we need to develop new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions.-
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.subjectDoubling dimension-
dc.subjectpolynomial time approximation scheme-
dc.subjectprize collecting-
dc.subjectSteiner tree problem-
dc.subjecttraveling salesman problem-
dc.titleA Unified PTAS for Prize Collecting TSP and Steiner Tree Problem 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/3378571-
dc.identifier.scopuseid_2-s2.0-85084759955-
dc.identifier.hkuros318366-
dc.identifier.volume16-
dc.identifier.issue2-
dc.identifier.spagearticle no. 24-
dc.identifier.epagearticle no. 24-
dc.identifier.isiWOS:000582615600009-
dc.publisher.placeUnited States-
dc.identifier.issnl1549-6325-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats