Maximum gradient embeddings and monotone clustering

Details Maximum gradient embeddings and monotone clustering Maximum gradient embeddings and monotone clustering

2006-06-26

arxiv.org/abs/cs/0606109v4

Combinatorica 30(5) (2010), 581--615

Computer Science

Data Structures and Algorithms

25 pages, 2 figures. Final version, minor revision of the previous one. To appear in "Combinatorica"

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Maximum gradient embeddings and monotone clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum gradient embeddings and monotone clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum gradient embeddings and monotone clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400120