Approximating min-sum k -clustering in metric spaces

DOI10.1145/380752.380754zbMath1323.68565OpenAlexW1994698869MaRDI QIDQ5175948

Danny Raz, Moses Charikar, Yair Bartal

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380754

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Continuous location (90B85) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25)

Related Items (17)

Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ Clustering to minimize the sum of cluster diameters ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? ⋮ Maximum gradient embeddings and monotone clustering ⋮ Data stability in clustering: a closer look ⋮ Advances in metric embedding theory ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Communication-aware processor allocation for supercomputers: Finding point sets of small average distance ⋮ Capacitated domination problem ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Center-based clustering under perturbation stability ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Sublinear‐time approximation algorithms for clustering via random sampling ⋮ A greedy approximation algorithm for the group Steiner problem

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Approximating min-sum k -clustering in metric spaces