A ptas for the steiner forest problem in doubling metrics

T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

We 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.


Read More: https://epubs.siam.org/doi/10.1137/16M1107206
Original languageEnglish
Pages (from-to)1705–1734
Number of pages30
JournalSIAM JOURNAL ON COMPUTING
Volume47
Issue number4
DOIs
Publication statusPublished - 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • PTAS
  • Steiner forest
  • doubling dimension

Fingerprint Dive into the research topics of 'A ptas for the steiner forest problem in doubling metrics'. Together they form a unique fingerprint.

Cite this