Low average distortion tree embeddings – part 2
SIT boardroom 11am friday
Two weeks ago julian covered a result of Fakcharoenphol, Rao, and Talwar for probabilistically embedding general metrics into tree metrics with low expected distortion, where the tree is not required to be a subgraph of the input graph. This week I will present the result of Alon, Karp, Peleg and West showing an embedding of a graph metric into a tree metric with low average distortion, with the restriction that the tree is a subgraph of the input graph.
The paper where this result appeared is titled “a graph theoretic game and its application to the k-server problem” (SIAM Journal on Computing 1995). I will only cover the relevant tree embedding result in this paper.
The presentation will be self-contained (i will not assume that you attended or remember anything from julian’s talk).