A new coreset framework for clustering

DOI10.1145/3406325.3451022MaRDI QIDQ6065182zbMATH OpenOpenAlexFDO

Authors Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-means\(k\)-medianclusteringcoresetsketch

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Given a metric space, the $(k,z)$-clustering problem consists of finding $k$ centers such that the sum of the of distances raised to the power $z$ of every point to its closest center is minimized. This encapsulates the famous $k$-median ($z=1$) and $k$-means ($z=2$) clustering problems. Designing small-space sketches of the data that approximately preserves the cost of the solutions, also known as emph{coresets}, has been an important research direction over the last 15 years. In this paper, we present a new, simple coreset framework that simultaneously improves upon the best known bounds for a large variety of settings, ranging from Euclidean space, doubling metric, minor-free metric, and the general metric cases.

Cited in

(24)

• Dominant-set clustering: a review
• Algorithms for fair \(k\)-clustering with multiple protected attributes
• scientific article; zbMATH DE number 3848646 (Why is no real title available?)
• On coresets for k-means and k-median clustering
• Coresets for Fuzzy K-Means with Applications
• Scaling up Kernel Grower Clustering Method for Large Data Sets via Core-sets
• Coresets for Discrete Integration and Clustering
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Tight FPT approximation for socially fair clustering
• New subset selection algorithms for low rank approximation: offline and online
• Coresets for kernel clustering
• FPT approximation for capacitated clustering with outliers
• Fully-scalable MPC algorithms for clustering in high dimension
• Parameterized approximation for robust clustering in discrete geometric spaces
• Space complexity of Euclidean clustering
• Clustering what matters in constrained settings (improved outlier to outlier-free reductions)
• Clustering what matters in constrained settings: improved outlier to outlier-free reductions
• An empirical evaluation of k-means coresets
• Approximation algorithms for continuous clustering and facility location problems
• Fully dynamic k-means coreset in near-optimal update time
• Dimension-free parameterized approximation schemes for hybrid clustering
• On approximability of _2² min-sum clustering
• Guessing efficiently for constrained subspace approximation
• Coresets for robust clustering via black-box reductions to vanilla case

This page was built for publication: A new coreset framework for clustering

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