kMedianClustering

kMedianClustering is a clustering technique that partitions a set of data points into k disjoint groups by selecting a representative point, called the median, for each cluster. The objective is to minimize the total sum of distances from each point to the median of its assigned cluster, where the distance metric can be any suitable metric such as Euclidean, Manhattan, or more generally any metric that satisfies the triangle inequality.

Unlike the more familiar k‑means algorithm, which optimizes the squared Euclidean distance to the centroids, k‑median uses the linear distance to medians. This distinction makes the k‑median objective more robust to outliers and yields solutions that are often closer to the geometric median of each cluster. Consequently, k‑median clustering is frequently preferred in applications where median‑based robustness is critical, such as in facility location, network design, and non‑Euclidean data analysis.

Exact solutions to the k‑median problem are NP‑hard even for Euclidean spaces with k fixed. Accordingly, practical algorithms rely on heuristics, such as Lloyd‑style iterations where medians are updated by selecting a data point that reduces the total cost, or local search techniques that exchange medians to improve the objective. Approximation algorithms exist that achieve constant‑factor guarantees; a classic example is the local search algorithm that achieves a 5‑approximation in general metric spaces. For special cases, such as one‑dimensional data, efficient linear‑time algorithms are available. Theoretical analysis typically focuses on approximation ratios, running‑time complexity, and the influence of the underlying metric space.

The k‑median formulation serves as a theoretical foundation for several applied problems, including clustering large geometric datasets, bandwidth allocation in networks, and clustering in high‑dimensional spaces where medians are preferable to means. Continuous research explores faster heuristics, improved approximation bounds, and extensions to dynamic settings where data points arrive incrementally.