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, ארצות הברית
משך הזמן: 2 נוב׳ 19983 נוב׳ 1998


כנסConfiguralble Computing: Technology and Applications
מדינה/אזורארצות הברית
עירBoston, MA

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Multi-embedding and path approximation of metric spaces'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי