Maximum gradient embeddings and monotone clustering

DOI10.1007/s00493-010-2302-zzbMath1274.30176arXivcs/0606109OpenAlexW2040023987MaRDI QIDQ1945290

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)

Related Items (3)

An introduction to the Ribe program ⋮ Snowflake universality of Wasserstein spaces ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms

Cites Work

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

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