Re:E-means: 10x faster k-means at equal loss
by nine_k on Tuesday November 10, 2026 @10:41AM
(#50441930)
> if it's the global minimum or not
Not impossible, just very expensive, because k-means is NP-hard, and finding the strictly optimal solution may require exponential time (or worse).
Re:E-means: 10x faster k-means at equal loss
by swann_bessa on Tuesday November 10, 2026 @10:51AM
(#50442100)
Yes, right. That's more rigorous to say it like that. Note that at the scales of the paper it is in practice impossible with today's computational means.
The answer is that e-means consistently finds a better solution than Lloyd. It's impossible to know if it's the global minimum or not. Finding the true global optimum is NP-hard, so no practical algorithm can guarantee that.