The optimization problem itself is known to be NP-hard, and thus the common approach is to search only for approximate solutions. A particularly well known approximate method is Lloyd's algorithm, often just referred to as ""k-means algorithm"" (although another algorithm introduced this name). It does however only find a local optimum, and is commonly run multiple times with different random initializations. Variations of "k"-means often include such optimizations as choosing the best of multiple runs, but also restricting the centroids to members of the data set ("k"-medoids), choosing medians ("k"-medians clustering), choosing the initial centers less randomly ("k"-means++) or allowing a fuzzy cluster assignment (fuzzy c-means).