Maximum gradient embeddings and monotone clustering

Manor Mendel, Assaf Naor

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


Let (X,dX) be an n-point metric space. We show that there exists a distribution D over non-contractive embeddings into trees f: X → T such that for every x ∈ X, → where C is a universal constant. Conversely we show that the above quadratic dependence on log n cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location.

שפה מקוריתאנגלית
עמודים (מ-עד)581-615
מספר עמודים35
כתב עתCombinatorica
מספר גיליון5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2010

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Maximum gradient embeddings and monotone clustering'. יחד הם יוצרים טביעת אצבע ייחודית.

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