A Complexity Theoretical Study of Fuzzy K -Means
Johannes Blömer, Sascha Brauer, Kathrin Bujna · ACM Transactions on Algorithms · 2020
The fuzzy K -means problem is a popular generalization of the well-known K -means problem to soft clusterings. In this article, we present the first algorithmic study of the problem going beyond heuristics. Our main result is that, assuming a constant number of clusters, there is a polynomial time approximation scheme for the fuzzy K -means problem. As a part of our analysis, we also prove the existence of small coresets for fuzzy K -means. At the heart of our proofs are two novel techniques developed to analyze the otherwise notoriously difficult fuzzy K -means objective function.