"...make it a practical replacement of the standard K-means as long as triangle inequality holds"
I haven't had time to read through this paper yet, but how often does triangle inequality not hold? This algorithm may not be as applicable as regular K-means due to this.
