0
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • $\begingroup$ Is $(V_1,V_2)$ supposed to be a partition? $\endgroup$
    – Jason Gaitonde
    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$
    – Emil Jeřábek
    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

0

Reset to default

Your Answer

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