Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.