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

Anupam Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages8
StatePublished - 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other2001 Operating Section Proceedings, American Gas Association
Country/TerritoryUnited States
CityDallas, TX


  • Algorithms
  • Measurement
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Steiner points in tree metrics don't (really) help'. Together they form a unique fingerprint.

Cite this