Answers are grounded in this paper and cite their sources.
The research demonstrates PLS-hardness of local search heuristics in Euclidean clustering contexts, signaling computational challenges.
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-hard. First, we show that the Hartigan-Wong method, which is essentially the Flip heuristic, for k-Means clustering is PLS-hard, even when k = 2. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set X ⊆ Rd; a problem which is equivalent to Min Sum 2-Clustering.
No takes yet. Share an insight, caveat, or question.
Manthey et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: