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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.