- Lecture
notes from our randomized algorithms course
(S11).
- Alon, Karp, Peleg,
West: A
Graph-Theoretic Game and its Application to the k-Server
Problem, SICOMP.
- Bartal: Probabilistic
Approximation of Metric Spaces and its Algorithmic
Applications, FOCS 96
Our presentation pretty
much followed his general construction.
- Fakcharoenphol, Rao,
Talwar, A
tight bound on approximating arbitrary metrics by tree>
metrics, STOC 03.
This paper gives the best
possible algorithm for the metric graph case.
- Abraham,
Neiman: Using
Petal-Decompositions to Build a Low Stretch Spanning
Tree.
This paper gives the current best algorithm
for the general graph case.
Some other low-diameter decomposition schemes:
And applications of low-stretch spanning trees to some problems: