K-median problem

The k-median problem is the problem of finding k centers such that the clusters formed by them are the most compact.

Formally, given a set of data points x, the k centers c_i are to be chosen so as to minimize the sum of the absolute values of the distances from each x to the nearest c_i.

The problem constitutes a better measure for the k-means clustering algorithm, and is widely used in applications such as facility location.