Multi-Embedding of Metric Spaces

Details Multi-Embedding of Metric Spaces Multi-Embedding of Metric Spaces

2004-08-02

arxiv.org/abs/cs/0408003v1

SIAM J. Comput. 34(1): 248-259, 2004

Computer Science

Data Structures and Algorithms

Scientific paper

10.1137/S0097539703433122

Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of its size. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size. We make a step in the direction of bypassing the lower bound on the distortion in terms of the size of the metric. We define "multi-embeddings" of metric spaces in which a point is mapped onto a set of points, while keeping the target metric of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Delta loglog Delta) where Delta is the aspect ratio of the metric. In particular, for expander graphs, we are able to obtain constant distortion embeddings into trees in contrast with the Omega(log n) lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings for two optimization problems: group Steiner tree and metrical task systems.

Affiliated with

Also associated with

No associations

Rating

Multi-Embedding of Metric Spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-Embedding of Metric Spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-Embedding of Metric Spaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299458