Loading...
Please wait, while we are loading the content...
Similar Documents
A Tight Lower Bound for the Steiner Point Removal Problem on Trees
| Content Provider | CiteSeerX |
|---|---|
| Author | Konjevod, Goran Xia, Donglin Chan, T. -H. Hubert Richa, Andrea |
| Abstract | Abstract. Gupta (SODA’01) 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 TS 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)). 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Unit Weight Complete Binary Tree Steiner Point Removal Problem Algorithm Guarantee Edge-weighted Tree Edge-weighted Tree T Tight Lower Bound Finite Tree Steiner Point Removal Upper Bound Spr Problem |
| Content Type | Text |
| Resource Type | Article |
