you're reading...

algorithms presentation this friday may 27

Low average distortion tree embeddings – part 2
taso viglas
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).



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: