A tight lower bound for the Steiner point removal problem on trees. (English) Zbl 1155.68394
Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 70-81 (2006).
Summary: A. Gupta [“Steiner points in tree metrics don’t (really) help”, in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, 220–227 (2001; Zbl 0990.05033)] considered the Steiner Point Removal (SPR) problem on trees. Given an edge-weighted tree \(T\) and a subset \(S\) of vertices called terminals in the tree, find an edge-weighted tree \(T_{S}\) on the vertex set \(S\) such that the distortion of the distances between vertices in \(S\) is small. His algorithm guarantees that for any finite tree, the distortion incurred is at most 8. Moreover, a family of trees, where the leaves are the terminals, is presented such that the distortion incurred by any algorithm for SPR is at least \(4(1 - o(1))\). In this paper, we close the gap and show that the upper bound 8 is essentially tight. In particular, for complete binary trees in which all edges have unit weight, we show that the distortion incurred by any algorithm for the SPR problem must be at least \(8(1 - o(1))\).
For the entire collection see [Zbl 1114.68006].
For the entire collection see [Zbl 1114.68006].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
