SOURCE-LINKED INTELLIGENCE

Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

arXiv · AI, language, vision and robotics · article · Sep 6, 2026 · UTC

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{$ε$-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{$(k,z)$-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresent

Read original source ↗ Open in workspace

recordType

paper

region

Global