Algorithmic Applications of Metric Embeddings

Anupam Gupta, Bell Labs

A large number of fundamental algorithmic problems involve optimization in finite metric spaces, and hence recent years have seen much work in understanding the structure of finite metric spaces, and particularly in finding meaningful ways to represent metrics so as to make them easy to work with, while retaining much of their inherent structure.

In this talk, I will talk about different ways to embed finite metrics into trees, and how these embeddings can be used to solve a variety of different problems. In particular, I will illustrate how tree embeddings can be used for emulating multicasts by unicasts, in building modular network routing algorithms, and in algorithms for graph partitioning and other optimization problems.