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.
reply> if it's the global minimum or not
replyNot impossible, just very expensive, because k-means is NP-hard, and finding the strictly optimal solution may require exponential time (or worse).
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.
reply