Embedding Metrics into the Plane
Piotr Indyk, MIT
June 24th 2005, Friday, 3:30pm, 4625 Wean Hall

Abstract:

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science.

Most of the known embedding results are "absolute", that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c. This is beneficial if one can guarantee small distortion c for all metrics Y in C. However, in many situations, the worst-case distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n-point star or an n-point cycle) are embeddable into X only with distortion linear in n.

Nevertheless, embeddings into low-dimensional spaces are important for many applications. Numerous techniques (notably Multidimensional Scaling) have been devised to solve this problem. However, existing algorithms typically do not guarantee finding the global minimum. This is not surprising, since many variants of the embedding problem are NP-complete.

In this talk, we consider "relative" (or "approximation") embedding problems. Here the goal is to design an approximation algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion comparable to the *best possible* distortion of an embedding of X into Y. I will present several algorithms, as well as hardness results, for relative embeddings into the *plane*. Specifically, I will show algorithms for relative embeddings of ultrametrics and spherical metrics, into the plane.

This is a joint work with Mihai Badoiu, Julia Chuzhoy and Tasos Sidiropoulos