TY - GEN

T1 - Maximum gradient embeddings and monotone clustering

AU - Mendel, Manor

AU - Naor, Assaf

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2007

Y1 - 2007

N2 - Let (X, dx) be an n-point metric space. We show that there exists a distribution & over non-contractive embeddings into trees f : X → T such that for every x ∈ X, ED [max v∈X\(x) dT(f(x), f(y))/dX(x, y)] < 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.

AB - Let (X, dx) be an n-point metric space. We show that there exists a distribution & over non-contractive embeddings into trees f : X → T such that for every x ∈ X, ED [max v∈X\(x) dT(f(x), f(y))/dX(x, y)] < 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.

UR - http://www.scopus.com/inward/record.url?scp=38049060509&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049060509&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-74208-1_18

DO - 10.1007/978-3-540-74208-1_18

M3 - Conference contribution

AN - SCOPUS:38049060509

SN - 9783540742074

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 242

EP - 256

BT - Approximation, Randomization, and Combinatorial Optimization

PB - Springer Verlag

T2 - 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007

Y2 - 20 August 2007 through 22 August 2007

ER -