Low dimensional embeddings of ultrametrics

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


In this note we show that every n-point ultrametric embeds with constant distortion in ℓpO(logn) for every ∞≥p≥1. More precisely, we consider a special type of ultrametric with hierarchical structure called a k-hierarchically well-separated tree (k-HST). We show that any k-HST can be embedded with distortion at most 1+O(1/k) in ℓp O(k2logn). These facts have implications to embeddings of finite metric spaces in low dimensional ℓp spaces in the context of metric Ramsey-type theorems.

שפה מקוריתאנגלית
עמודים (מ-עד)87-92
מספר עמודים6
כתב עתEuropean Journal of Combinatorics
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2004
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Funding Information:
Y. Bartal and N. Linial are supported in part by a grant from the Israeli National Science Foundation. M. Mendel is supported in part by the Landau Center.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Low dimensional embeddings of ultrametrics'. יחד הם יוצרים טביעת אצבע ייחודית.

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