# Complexity of the distance between the average vector of two subsets

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!

• Is $(V_1,V_2)$ supposed to be a partition? May 18, 2022 at 17:12
• 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. May 18, 2022 at 20:08
• @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. May 21, 2022 at 14:30
• @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/… May 21, 2022 at 14:33