K-medians and K-medoids are a variants of K-means clustering algorithm. The both minimize the sum of the distances from the centroids to the points, but the K-modoids algorithm requires that the center of each cluster be a sample point. Both problems can be solved using EM type methods.