Maximum gradient embeddings and monotone clustering
From MaRDI portal
Publication:1945290
DOI10.1007/s00493-010-2302-zzbMath1274.30176arXivcs/0606109MaRDI QIDQ1945290
Publication date: 5 April 2013
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0606109
clustering problems with monotone costs; embedding metric spaces into trees; maximum gradient embeddings
Related Items
Snowflake universality of Wasserstein spaces, An introduction to the Ribe program, 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 1
- 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
