Maximum gradient embeddings and monotone clustering

Let (X,d_X) 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.