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
مستوى الصوت25
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 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'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا