# On the k-Means/Median Cost Function

arXiv: https://arxiv.org/abs/1704.05232 · HTML: https://mlsanity.com/paper/1704.05232/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Common-Center Geometry and Certified Radial Reconstruction for Energy-Form Full Conformal Regions](https://mlsanity.com/paper/2608.24964/) (2026)

## Abstract (arXiv)

In this work, we study the k-means cost function. Given a dataset X subseteq ℝd and an integer k, the goal of the Euclidean k-means problem is to find a set of k centers C subseteq ℝd such that Phi(C, X) equiv sumx ∈ X minc ∈ C ||x - c||2 is minimized. Let Delta(X,k) equiv minC subseteq ℝd Phi(C, X) denote the cost of the optimal k-means solution. For any dataset X, Delta(X,k) decreases as k increases. In this work, we try to understand this behaviour more precisely. For any dataset X subseteq ℝd, integer k ≥ 1, and a precision parameter varepsilon > 0, let L(X, k, varepsilon) denote the smallest integer such that Delta(X, L(X, k, varepsilon)) ≤ varepsilon · Delta(X,k). We show upper and lower bounds on this quantity. Our techniques generalize for the metric k-median problem in arbitrary metric spaces and we give bounds in terms of the doubling dimension of the metric. Finally, we observe that for any dataset X, we can compute a set S of size O left(L(X, k, varepsilon/c) right) using D2-sampling such that Phi(S,X) ≤ varepsilon · Delta(X,k) for some fixed constant c. We also discuss some applications of our bounds.