Piotr Indyk
MIT
Embedding Metrics into the Plane
Friday, June 24th
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. For more background and related results, especially on
embeddings into the *line*, see the thesis of Kedar Dhamdhere (defense
scheduled for one and a half hours before this talk).
