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
مستوى الصوت30
رقم الإصدار5
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - سبتمبر 2010


أدرس بدقة موضوعات البحث “Maximum gradient embeddings and monotone clustering'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا