File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A PTAS for the Steiner Forest Problem in Doubling Metrics

TitleA PTAS for the Steiner Forest Problem in Doubling Metrics
Authors
KeywordsApproximation algorithms
Doubling metrics
Steiner forest problem
Issue Date2018
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
SIAM Journal on Computing, 2018, v. 47 n. 4, p. 1705-1734 How to Cite?
AbstractWe achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115-124]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [Y. Bartal, L. Gottlieb, and R. Krauthgamer, in STOC, ACM, 2012, pp. 663-672] and [T-H. H. Chan and S.-H. Jiang, in SODA, SIAM, 2016, pp. 754-765]. However, extending previous approaches requires overcoming several nontrivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be near' the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as adaptive cells' to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed uniform cells' in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115-124], where techniques cannot be readily applied to doubling metrics. © 2018 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/290736
ISSN
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 2.143
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, THH-
dc.contributor.authorHU, S-
dc.contributor.authorJIANG, SHC-
dc.date.accessioned2020-11-02T05:46:23Z-
dc.date.available2020-11-02T05:46:23Z-
dc.date.issued2018-
dc.identifier.citationSIAM Journal on Computing, 2018, v. 47 n. 4, p. 1705-1734-
dc.identifier.issn0097-5397-
dc.identifier.urihttp://hdl.handle.net/10722/290736-
dc.description.abstractWe achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115-124]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [Y. Bartal, L. Gottlieb, and R. Krauthgamer, in STOC, ACM, 2012, pp. 663-672] and [T-H. H. Chan and S.-H. Jiang, in SODA, SIAM, 2016, pp. 754-765]. However, extending previous approaches requires overcoming several nontrivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be near' the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as adaptive cells' to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed uniform cells' in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115-124], where techniques cannot be readily applied to doubling metrics. © 2018 Society for Industrial and Applied Mathematics.-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP-
dc.relation.ispartofSIAM Journal on Computing-
dc.rights© [2018] Society for Industrial and Applied Mathematics. First Published in [SIAM Journal on Computing] in [v. 47 n. 4], published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectApproximation algorithms-
dc.subjectDoubling metrics-
dc.subjectSteiner forest problem-
dc.titleA PTAS for the Steiner Forest Problem in Doubling Metrics-
dc.typeArticle-
dc.identifier.emailChan, THH: hubert@cs.hku.hk-
dc.identifier.authorityChan, THH=rp01312-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/16M1107206-
dc.identifier.scopuseid_2-s2.0-85053602439-
dc.identifier.hkuros318363-
dc.identifier.volume47-
dc.identifier.issue4-
dc.identifier.spage1705-
dc.identifier.epage1734-
dc.identifier.isiWOS:000443195600015-
dc.publisher.placeUnited States-
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats