Maximum gradient embeddings and monotone clustering

Manor Mendel, Assaf Naor

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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
Issue number5
StatePublished - Sep 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


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

Cite this