Maximum gradient embeddings and monotone clustering

Manor Mendel, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings
Pages242-256
Number of pages15
StatePublished - Dec 1 2007
Externally publishedYes
Event10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United States
Duration: Aug 20 2007Aug 22 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4627 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
CountryUnited States
CityPrinceton, NJ
Period8/20/078/22/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Maximum gradient embeddings and monotone clustering'. Together they form a unique fingerprint.

  • Cite this

    Mendel, M., & Naor, A. (2007). Maximum gradient embeddings and monotone clustering. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings (pp. 242-256). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4627 LNCS).