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.
