Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer.

Let's consider the following problem

$\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) \|x_i - \mu \|_2^2$

where: $F:[0, 1] \rightarrow R$ is the $\alpha$-threshold, i.e. $F(z) = 1$ is $z \le \alpha$ and $F(z) = 0$ otherwise; and $\pi$ is the ascending permutation of the $i$s based on the values of $\|x_i-\mu\|_2^2$.

I guess one way to reformulate the problem is the following: find the mean of the size-$\alpha n$ subset of elements with the smallest variance.

I'm not an expert and I'm wondering if this problem is $NP$-hard. For $d=1$ it admits a simple polinomial time algorithm, but in the general case, I suspect it doesn't.

  • $\begingroup$ Did you look at the NP-hardness of the k-means problem? That could be a starting point. $\endgroup$
    – usul
    Jul 13, 2020 at 14:10


Your Answer

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

Browse other questions tagged or ask your own question.