Answer: k-Medoids (PAM) vs k-Means

Criterion	k-Means	k-Medoids (PAM)
Proposed center	Centroid: mean vector of the cluster (arithmetic mean — not necessarily a point in the data set)	Medoid: an actual data object within the cluster that is the most centrally located (minimises total distance to all other objects in the cluster)
Robust to outliers/noise	No — outliers affect the mean and can distort the centre	Yes — the medoid is a real point, so isolated/outlying points affect it much less
Suitable data type	numerical (mean requires numbers)	any — including categorical data (only distances/ dissimilarities needed)
Complexity	cheaper for low/$| often$O(n^2)$ or worse — it must evaluate all candidate medoid swaps
Output	a hard cluster line through "data point at the boundary"	one of the real existing data objects

When to use k-medoids? When outliers/noise are present, or when the data is not numeric (e.g., some categorical/mixed data), or when the interpretation as an existing prototype is necessary.

Summary: k-Means uses a mean (centroid, often invented point); k-Medoids uses a medoid — an existing representative object — making it robust to outliers and usable with non-numeric dissimilarity matrices.