NP-hardness of Euclidean sum-of-squares clustering

By Daniel J. Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat. Machine-mediated learning, 2008

1,037 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/525ac8da0afe2ba149b0e26c07bf9da1fa62650d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Locally Private k-Means in One Round (2021, background): “Computationally, ﬁnding optimal k -means cluster centers is NP-hard (e.g., Aloise et al., 2009) and the best known polynomial-time algorithm achieves an approximation ratio of 6 .”
A Comprehensive Survey of Loss Functions in Machine Learning (2020, background): “There are two sets of variables { r ik } and { k }( i = 1, … , N ; k = 1, … , K ) , minimizing this loss is a NP hard problem [49], so k-means adopts greedy strategy and uses iterative optimization to approximate the solution.”
Clustering with Bregman Divergences: an Asymptotic Analysis (2016, background): “Finding the global minimum of loss function is a NP-hard problem [1, 17].”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “Achieving the optimal solution is, in general, NP-Hard [3].”
Consistency of spectral clustering in stochastic block models (2013, neutral): “In this paper we consider the k -means clustering, deﬁned as ( Θ , X ) = arg min b b b It is known that ﬁnding a global minimizer for the k -means problem (2) is NP-hard (see, e.g., Aloise et al., 2009).”
Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming (2011, background): “However, the problem is NP-hard in a general Euclidean space, even when the number of clusters k is 2 (Aloise et al., 2009; Dasgupta and Freund, 2009), or when the dimensionality is 2 (Mahajan et al., 2009).”
Kernel Archetypal Analysis for Clustering Web Search Frequency Time Series (2014, methodology): “Similar to k-means clustering and NMF, the problem in (3) is an instance of a Euclidean sum of square clustering problem and as such NP-hard [2].”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, neutral): “Solving k-means to optimality is generally NP-Hard Aloise et al. (2009), so many efficient heuristics and approximation algorithms have been developed.”
Balanced K-Means for Clustering (2014, background): “Euclidean sum-of-squares clustering is an NP-hard problem [1], which groups n data points into k clusters so that intra-cluster distances are low and inter-cluster distances are high.”
A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm (2012, background): “In fact, this non-convex optimization problem is proven to be NP-hard even for K = 2 [4] or D = 2 [5].”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, background): “There is significant evidence to indicate that even without the requirement on privacy, exact optimization of these objective function in Euclidean spaces might be computationally infeasible (Dasgupta, 2008; Aloise et al., 2009): The best-known result in this line of research is (9 + ε)×OPT by the l”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “NP-hardness of Euclidean sum-of-squares clustering.”