<p>Given a vector set <span class="math-container">$V=\{v_i\}_{i=1}^n$</span> with <span class="math-container">$n$</span> vectors, where <span class="math-container">$v_i\in \mathbb{R}^d$</span> is a vector, the target is to select two subsets <span class="math-container">$V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$</span> and <span class="math-container">$V_2=\{v_k\}_{k=1}^{|V_2|} \subset V$</span> to maximize the distance between the average vector of two selected subsets as follows:</p>
<p><span class="math-container">$$\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}$$</span></p>
<p>Is this problem is np-hard and have some good bound, such as constant? Thanks!</p>

CC BY-SA 4.0
2022-05-18T17:12:42.150Z
Is $(V_1,V_2)$ supposed to be a partition?
Jason Gaitonde
CC BY-SA 4.0
2022-05-18T20:08:32.087Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-05-21T14:30:45.590Z
@Emil Jeřábek, Thanks a lot. You are right! I have voted for your comments. And I have posted the second version here,  https://cstheory.stackexchange.com/questions/51491/the-second-version-complexity-of-the-distance-between-the-average-vector-of-two   could you think this variant can be solved very quickly.
Refrain
CC BY-SA 4.0
2022-05-21T14:33:28.123Z
@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 https://cstheory.stackexchange.com/questions/51491/the-second-version-complexity-of-the-distance-between-the-average-vector-of-two
Refrain
<np-hardness><approximation-algorithms>
Complexity of the distance between the average vector of two subsets
Refrain
# Complexity of the distance between the average vector of two subsets

(Asked by: username_0 on 2022-05-18)

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!

**Tags:** np-hardness, approximation-algorithms

> **Comments:**
> **username_1**: Is $(V_1,V_2)$ supposed to be a partition?  
> **username_2**: 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.  
> **username_0**: @username_2, Thanks a lot. You are right! I have voted for your comments. And I have posted the second version here,  https://cstheory.stackexchange.com/questions/51491/the-second-version-complexity-of-the-distance-between-the-average-vector-of-two   could you think this variant can be solved very quickly.  
> **username_0**: @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 https://cstheory.stackexchange.com/questions/51491/the-second-version-complexity-of-the-distance-between-the-average-vector-of-two  

---

## 0 answers

