Metric k-minsum clustering solved efficiently for small k values
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Data Structures and AlgorithmsComputational Complexity
Summary
Clustering in data means grouping points that are close to each other. This paper focuses on a particular way to measure clustering quality called k-minsum, which had unclear computational difficulty. The authors present a new method that approximates good clusters quickly when the number of clusters k grows slowly, running faster than reading all data in some cases. They also show that similar fast methods are unlikely for related clustering problems like k-median, highlighting a surprising difference between these approaches.
What this means in practice
- •For data scientists: Use fast algorithms to approximate clustering models on large datasets with a controlled number of clusters, saving computation time.
- •For big data engineers: Integrate sublinear time clustering algorithms for scalable analysis when working with very large metric data and a small number of clusters.
Authors
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
Abstract
Metric $k$-minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achieved fornother clustering criteria in the past three decades. In this paper we give an efficient approximation scheme for this problem that runs in sublinear time for mildly increasing $k$, and thus is fixed parameter tractable with respect to the parameter $k$. We complement this result by showing that similar algorithms are unlikely to exist for the closely related problems $k$-median and balanced $k$-median, assuming popular fine-grained complexity conjectures. Specifically, we show that no sublinear time algorithm with small approximation factors can exist even for $2$-median and balanced $2$-median. It was previously known that no efficient PTAS can exist for $k$-median and our results show a strong and perhaps surprising separation between the $k$-minsum clustering problem and $k$-median even in the sublinear regime. Our upper bounds improve qualitatively upon decades old results. Our lower bounds establish the first use of the Distributed PCP framework to clustering problems.