Multi-embedding and path approximation of metric spaces

Yair Bartal, Manor Mendel

نتاج البحث: نتاج بحثي من مؤتمرمحاضرةمراجعة النظراء


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.

اللغة الأصليةالإنجليزيّة
عدد الصفحات10
حالة النشرنُشِر - 2003
منشور خارجيًانعم
الحدثConfiguralble Computing: Technology and Applications - Boston, MA, الولايات المتّحدة
المدة: ٢ نوفمبر ١٩٩٨٣ نوفمبر ١٩٩٨


!!ConferenceConfiguralble Computing: Technology and Applications
الدولة/الإقليمالولايات المتّحدة
المدينةBoston, MA


أدرس بدقة موضوعات البحث “Multi-embedding and path approximation of metric spaces'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا