A PTAS for the Steiner Forest Problem in Doubling Metrics
Authors:
- T-H. Hubert ChanTCT-H. Hubert Chan
- Shuguang HuSHShuguang Hu
- Shaofeng H.-C. JiangSJShaofeng H.-C. Jiang
- 1 October 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 810-819
Abstract
We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein and Mathieu]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [STOC 2012: Bartal, Gottlieb and Krauthgamer] and [SODA 2016: Chan and Jiang]. However, extending previous approaches requires overcoming several non-trivial 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 the FOCS 2008 paper, whose techniques cannot be readily applied to doubling metrics.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Node-Weighted Steiner Tree and Group Steiner Tree in Planar GraphsACM Transactions on Algorithms, 2014
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded TreewidthJournal of the ACM, 2011
- Euclidean Prize-Collecting Steiner ForestAlgorithmica, 2011
- The Steiner tree problem on graphs: Inapproximability resultsTheoretical Computer Science, 2008
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree ProblemJournal of Algorithms, 2000
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on NetworksSIAM Journal on Computing, 1995
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- Steiner minimal trees for regular polygonsDiscrete & Computational Geometry, 1987
- Steiner minimal tree for points on a circleProceedings of the American Mathematical Society, 1985