Embeddings of finite metrics
Anupam Gupta, Alistair Sinclair · 2000
The study of metric embeddings has recently received much attention due to both its mathematical and its computational significance. Many of the questions that arise involve embedding a given metric into some natural “target” metric so as to preserve distances approximately. The emphasis of this thesis is to study the relationship between the topology of graphs and how well they can be embedded into a variety of target spaces. The first part of this thesis studies embeddings of metrics into e 1-space and into distributions over trees, both of which have had much impact on algorithms in the past few years. In Chapter 3, it is shown that a sharp dichotomy exists in the nature of embeddings of graphs into these two seemingly similar target spaces as the topology of the graph varies. While outerplanar graphs can be embedded well into both e1-space and probability distributions over trees, the same is not true for the next natural class of graphs, that of series-parallel graphs. These graphs can be embedded into e1 with constant distortion, but inevitably suffer a logarithmic distortion when embedded into tree distributions. Embeddings into other natural target spaces are also studied. It is shown that constant-degree expander graphs cannot be embedded into the so-called “negative type spaces” with sub-logarithmic distortion, a fact that keeps alive the hope that constant factor approximation algorithms can be found for the important Sparsest Cut problem via the approach of metric embeddings. Planar graphs are shown to have constant distortion embeddings into negative type spaces. It is also shown how to embed trees into low-dimensional Euclidean spaces with a distortion that is nearly optimal, thus settling an open problem of Matousek. In recent work, Feige has generalized the notion of distance-preserving embeddings in a natural way to embeddings that in addition preserve volumes of sets of points. The first poly-logarithmic approximation algorithms for the Bandwidth Minimization problem have been based on these embeddings. In Chapter 5, this concept is generalized slightly to that of partial volume-respecting embeddings, which are used to give extremely simple approximation algorithms for Bandwidth Minimization on trees that improve on previous approximation guarantees. An alternative construction for volume-respecting embeddings for general graphs is given, which extends an algorithm given by Rao for the special case of planar graphs. The last chapter of this thesis shows that metrics generated by trees are almost as expressive as their sub-metrics. In particular, it is shown that the metric induced by any subset of vertices of a tree can be approximated well by a tree on just that subset. As a by-product of this structural result, one can obtain efficient algorithms for efficiently emulating multicast transmissions using unicasts incurring only a constant-factor overhead in the transmission delay, as well as simple combinatorial proofs of lower bounds on embedding graphs with large girth into trees.