Dimension Reduction for Ultrametrics

Yair Bartal; Manor Mendel

Dimension Reduction for Ultrametrics

Yair Bartal
, Manor Mendel

פרסום מחקרי: תוצר מחקר מכנס › הרצאה › ביקורת עמיתים

תקציר

We prove that an ultrametric on n points can be embedded in l _p ^d with distortion at most 1 + ε, and d = O(ε ^-2log n). This bound matches the best known bound for the special case of an equilateral space.

שפה מקורית	אנגלית
עמודים	657-658
מספר עמודים	2
סטטוס פרסום	פורסם - 2004
פורסם באופן חיצוני	כן
אירוע	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., ארצות הברית משך הזמן: 11 ינו׳ 2004 → 13 ינו׳ 2004

כנס

כנס	Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
מדינה/אזור	ארצות הברית
עיר	New Orleans, LA.
תקופה	11/01/04 → 13/01/04

קבצים וקישורים אחרים

Link to publication in Scopus

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

@conference{f7c572b4a02548adaef2ee03098ad541,

title = "Dimension Reduction for Ultrametrics",

abstract = "We prove that an ultrametric on n points can be embedded in l p d with distortion at most 1 + ε, and d = O(ε -2log n). This bound matches the best known bound for the special case of an equilateral space.",

author = "Yair Bartal and Manor Mendel",

year = "2004",

language = "אנגלית",

pages = "657--658",

note = "Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 11-01-2004 Through 13-01-2004",

}

TY - CONF

T1 - Dimension Reduction for Ultrametrics

AU - Bartal, Yair

AU - Mendel, Manor

PY - 2004

Y1 - 2004

N2 - We prove that an ultrametric on n points can be embedded in l p d with distortion at most 1 + ε, and d = O(ε -2log n). This bound matches the best known bound for the special case of an equilateral space.

AB - We prove that an ultrametric on n points can be embedded in l p d with distortion at most 1 + ε, and d = O(ε -2log n). This bound matches the best known bound for the special case of an equilateral space.

UR - https://www.scopus.com/pages/publications/1842487383

M3 - ???researchoutput.researchoutputtypes.contributiontoconference.paper???

AN - SCOPUS:1842487383

SP - 657

EP - 658

T2 - Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 11 January 2004 through 13 January 2004

ER -

Dimension Reduction for Ultrametrics

תקציר

כנס

קבצים וקישורים אחרים

טביעת אצבע

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