Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|} \subset V$ to maximize the distance between the average vector of two selected subsets as follows:

$$\max_{V_1,V_2}{\left\|\frac{1}{|V_1|}\sum_{v_j \in V_1}{v_j}-\frac{1}{|V_2|}\sum_{v_k\in V_2}{v_k}\right\|_2}$$

Is this problem is np-hard and have some good bound, such as constant? Thanks!

  • $\begingroup$ Is $(V_1,V_2)$ supposed to be a partition? $\endgroup$ May 18, 2022 at 17:12
  • 1
    $\begingroup$ The norm of a convex combination of a set of vectors is at most the maximum of their norms. It follows that your maximal distance is attained for $|V_1|=|V_2|=1$, that is, it is just the diameter of $V$. Thus, you can compute it in polynomial time. $\endgroup$ May 18, 2022 at 20:08
  • $\begingroup$ @Emil Jeřábek, Thanks a lot. You are right! I have voted for your comments. And I have posted the second version here, cstheory.stackexchange.com/questions/51491/… could you think this variant can be solved very quickly. $\endgroup$
    – Refrain
    May 21, 2022 at 14:30
  • $\begingroup$ @J.G, thanks! $V_1$ and $V_2$ can be overlapped or not. This problem can be solved in polynomial time. I have posted a variant of this here cstheory.stackexchange.com/questions/51491/… $\endgroup$
    – Refrain
    May 21, 2022 at 14:33


Your Answer

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