Maximum gradient embeddings and monotone clustering

DOI10.1007/S00493-010-2302-ZMaRDI QIDQ1945290zbMATH OpenOpenAlexFDO

Authors Assaf Naor, Manor Mendel

Publication date 5 April 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0606109

zbMATH Keywords

clustering problems with monotone costsembedding metric spaces into treesmaximum gradient embeddings

Mathematics Subject Classification ID

Approximation algorithms (68W25) Geometric embeddings of metric spaces (30L05)

Abstract: 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.

Recommendations

• Maximum Gradient Embeddings and Monotone Clustering
• Multiembedding of Metric Spaces
• A tight bound on approximating arbitrary metrics by tree metrics
• A tight bound on approximating arbitrary metrics by tree metrics
• scientific article; zbMATH DE number 2079366

Cites work

• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 2079405 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A constant-factor approximation algorithm for the k-median problem
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• A tight bound on approximating arbitrary metrics by tree metrics
• An approximation algorithm for the fault tolerant metric facility location problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating min-sum k -clustering in metric spaces
• Approximation Algorithms for the 0-Extension Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering to minimize the sum of cluster diameters
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Euclidean quotients of finite metric spaces
• Extending Lipschitz functions via random metric partitions
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Combinatorial Algorithms for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Lower-stretch spanning trees
• Measured descent: A new embedding method for finite metrics
• Multiembedding of Metric Spaces
• Oblivious network design
• On the impossibility of dimension reduction in l ₁
• Ramsey partitions and proximity data structures
• The concentration of measure phenomenon

Cited in

(5)

• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• Maximum Gradient Embeddings and Monotone Clustering
• Clustering, Hamming Embedding, Generalized LSH and the Max Norm
• An introduction to the Ribe program
• Snowflake universality of Wasserstein spaces

This page was built for publication: Maximum gradient embeddings and monotone clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945290)