MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the plane so as to minimize the distances (or squares of distances) to the points $p_i$, i.e. to minimize the quantity $\sum_{i=1}^{N} \min_j \| x_j - p_i \|$ (I am not requiring that the $x_j$'s be a subset of the $p_i$'s; they can lie anywhere in the plane). Obviously this problem has many practical applications.

My question is: let's suppose we impose some constraints on the first or second moments of $x_1,\dots,x_k$, i.e. require that $\frac{1}{k}\sum_j x_j = x_0$ for some fixed point $x_0$, or that $\frac{1}{k} \sum_j \|x_j - \bar{x}\|^2 \leq S^2$ for some given threshold $S^2$. Is there any conceivable practical scenario where this might arise?

I am not asking for assistance in solving this problem -- I'm really just interested in any thoughts on contexts where it might occur.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.