All the k-means algorithms are trying in one way or another to find k points such that if you would map any point from the original data set to it's closest point from those k points you would minimize the sum of squared distances to those points.

**The problem with this cost function:**

Imagine the following 1 dimensional case (i.e., numbers instead of vectors) with k = 2. Let's call the ground truth points A and B such that A = -1 and B = 1. And let's call the points an optimal k-means algorithm would return C and D such that C and D correspond to A and B respectively. Now let's say we have a large dateset that was created from points around A and B with some normal distribution. Assuming the variance is large enough we expect that a percentage of points from A would be positive and a percentage of the points from B would be negative, because of that those points would be mapped to the wrong points and that would make C and D closer to each-other than A and B and as the variance increases C and D both approaching 0.

**Solution to this problem?**

This problem sounds so fundamental to me that i was sure I could find something about it however when I searched I couldn't find anything on this problem. So my question is is there any paper/algorithm that addresses this problem and tries to solve this? Even for special cases when assuming normal distribution of the data or having any other assumptions for the distribution of the data? It's just weird to me that I didn't find anywhere any mention of this problem what so ever.