K-medians is typically used with Manhattan distance rather than Euclidean distance. Why is this?
The mean is a least squares estimator of location. It is appropriate to use with squared deviations (i.e. squared Euclidean distance, k-means algorithm)
The median is the best absolute deviation estimator or location. It is appropriate to use with absolute deviations (i.e. Manhattan distance, k-medians algorithm)
The medoid (c.f. PAM) is a smallest-distance estimator, it works with arbitrary distances. (K-medoids algorithm = PAM).