Multi-embedding and path approximation of metric spaces

Metric embeddings have become a frequent tool in the design of algorithms. The applicability is often dependent on how high the embedding's distortion is. For example embedding into ultrametrics (or arbitrary trees) requires linear distortion. Using probabilistic metric embeddings, the bound reduces to O(log n log log n). Yet, the lower bound is still logarithmic. We make a step further in the direction of by-passing this difficulty. We define "multi-embeddings" of metric spaces where a point is mapped onto a set of points, while keeping the target metric being of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Δ log log Δ) where Δ is the (normalized) diameter, and probabilistically O(log n log log log n). In particular, for expander graphs, we are able to obtain constant distortions embeddings into trees vs. the Ω(log n) lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings by obtaining improvements for two well-known problems: group Steiner tree and metrical task systems.