Both of them utilize expectation-maximization strategy to converge to a minimum error condition. While K-Medoids require the cluster centters to be centroids, in k-Means the centers could be anywhere in the sample space. k-Medoids is more robust to outliners than k-Means therefore results in more quality clustering. It is also computationally more complex.