Maximum gradient embeddings and monotone clustering

Manor Mendel, Assaf Naor

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 in X, the expectation wi…