TY - GEN

T1 - Steiner points in tree metrics don't (really) help

AU - Gupta, Anupam

PY - 2001

Y1 - 2001

N2 - Consider an edge-weighted tree T = (V, E, w : E ↣ R +), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\R are colored black (and called the Steiner nodes). The shortest-path distance according to the edge-weights defines a metric dT on the vertex set V. We now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* ↣ R +), this time on just the red vertices so that the shortest-path metric dT* induced by T* on the vertices in R is "close" to the metric dT restricted to the red vertices? I.e., does there exist a weighted tree T* = (R, E*, c*) and a (small) constant &agr; such that dT(u, v) ≤ dT* (u, v) ≤ dT (u, v) for any two red vertices u, &squv; a R? We answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with &agr; ≤ 8. We also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least &OHgr;(g) when approximated by a tree.

AB - Consider an edge-weighted tree T = (V, E, w : E ↣ R +), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\R are colored black (and called the Steiner nodes). The shortest-path distance according to the edge-weights defines a metric dT on the vertex set V. We now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* ↣ R +), this time on just the red vertices so that the shortest-path metric dT* induced by T* on the vertices in R is "close" to the metric dT restricted to the red vertices? I.e., does there exist a weighted tree T* = (R, E*, c*) and a (small) constant &agr; such that dT(u, v) ≤ dT* (u, v) ≤ dT (u, v) for any two red vertices u, &squv; a R? We answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with &agr; ≤ 8. We also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least &OHgr;(g) when approximated by a tree.

KW - Algorithms

KW - Measurement

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=65549088171&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65549088171&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:65549088171

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 220

EP - 227

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -