A bad instance for k-means++

k-means++ is a seeding technique for the k-means method with an expected approximation ratio of O(logk), where k denotes the number of clusters. Examples are known on which the expected approximation ratio of k-means++ is Ω(logk), showing that the upper bound is asymptotically tight. However, it remained open whether k-means++ yields a constant approximation with probability or even with constant probability. We settle this question and present instances on which k-means++ achieves an approximation ratio no better than (2/3−ε)⋅logk with probability exponentially close to  1.