Maximum gradient embeddings and monotone clustering
<|reference_start|>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 in X, the expectation with respect to D of the maximum over y in X of the ratio d_T(f(x),f(y)) / d_X(x,y) is at most C (log n)^2, 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.<|reference_end|>
@article{mendel2006maximum,
    title={Maximum gradient embeddings and monotone clustering},
    author={Manor Mendel, Assaf Naor},
    journal={Combinatorica 30(5) (2010), 581--615},
    year={2006},
    doi={10.1007/s00493-010-2302-z},
    archivePrefix={arXiv},
    eprint={cs/0606109},
    primaryClass={cs.DS}
}