Maximum gradient embeddings and monotone clustering

Manor Mendel, Assaf Naor

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)581-615
Number of pages35
JournalCombinatorica
Volume30
Issue number5
DOIs
StatePublished - Sep 2010

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Maximum gradient embeddings and monotone clustering'. Together they form a unique fingerprint.

  • Cite this