<p>This problem is indeed a single objective optimization problem in the case of <span class="math-container">$W=0$</span>.(the second term become zero) If the problem is NP-hard in the single objective case, then it is also NP-hard in the multi-objective case.</p>
<p>=========================================</p>
<p>Edit : I saw your question in the following link for the single-objective optimization version and it is in P.</p>
<p><a href="https://cstheory.stackexchange.com/questions/51475/complexity-of-the-distance-between-the-average-vector-of-two-subsets">Complexity of the distance between the average vector of two subsets</a></p>
<p>However the problem is still NP-hard, can be reduced from the Equal Sum Subset problem which is known to be NP-hard.</p>
<p>In this problem, we are given a set of positive integers and we ask for two disjoint subset with equal sum of elements.</p>
<p>Let given instance of the Equal Sum Subset problem (B) be <span class="math-container">$\{a_1,\cdots,a_m\}$</span>.</p>
<p>Let <span class="math-container">$\lambda = 1$</span>, <span class="math-container">$n=2m$</span>, <span class="math-container">$d=m+1$</span>. Each <span class="math-container">$v_i$</span> is a standard basis <span class="math-container">$e_i$</span> for <span class="math-container">$i=1,\cdots,n$</span>. This make us possible to arbitrarily set the value of <span class="math-container">$Wv_i$</span>. Let <span class="math-container">$M&gt; n^2$</span> be a sufficiently large number.</p>
<p>The first <span class="math-container">$m$</span> coordinate of <span class="math-container">$Wv_i$</span> is <span class="math-container">$Me_i$</span> for <span class="math-container">$1 \le i \le m$</span> and <span class="math-container">$Me_{i-m}$</span> for <span class="math-container">$m+1 \le i \le 2m$</span>.</p>
<p>The last coordinate of <span class="math-container">$Wv_i$</span> is <span class="math-container">$Ma_i$</span> for <span class="math-container">$1 \le i \le m$</span> and <span class="math-container">$0$</span> otherwise.</p>
<p>My claim is that the multi-objective problem (A) has positive optimal value if and only if the answer of the Equal Sum Subset problem is 'yes'.</p>
<p>Let's make some observations. Let the optimal subsets be <span class="math-container">$V_1^*$</span> and <span class="math-container">$V_2^*$</span>.</p>
<p>First, note that if both subset <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> are empty, the objective value is <span class="math-container">$0$</span>.</p>
<p>Second, the first term of A is at most <span class="math-container">$1$</span>.(from the single-objective case)</p>
<p>Third, if <span class="math-container">$v_i \in V_1^*$</span>(<span class="math-container">$V_2^*$</span>, respectively) for some <span class="math-container">$1 \le i \le m$</span>, <span class="math-container">$v_{m+i}$</span> must in <span class="math-container">$V_2^*$</span>(<span class="math-container">$V_1^*$</span>, respectively). The converse is also true. Otherwise, the absolute value of the <span class="math-container">$i$</span>th coordinate of the vector in the second term is larger than <span class="math-container">$M/n^2 &gt; 1$</span> and in this case the objective value must be negative. This implies <span class="math-container">$|V_1| = |V_2|$</span>.</p>
<p>Fourth, Let <span class="math-container">$V_i^* \cap [1,n] = S_i$</span> for <span class="math-container">$i=1,2$</span>. Following the third observation, the last coordinate of the vector in the second term is <span class="math-container">$0$</span> if <span class="math-container">$|S_1|=0$</span>, and <span class="math-container">$M\frac{|\sum_{i \in S_1}a_i - \sum_{j \in S_2}a_j |}{|S_1|}$</span> otherwise.</p>
<p>If the answer of (B) is no, the absolute value of the last coordinate of the vector in the second term is at least <span class="math-container">$M/m &gt; 1$</span> if <span class="math-container">$|S_1| &gt; 0$</span>, hence the optimal value is <span class="math-container">$0$</span>.</p>
<p>If the answer of the (B) is yes, let the corresponding index set of the two set be <span class="math-container">$S_1$</span> and <span class="math-container">$S_2$</span>. Let <span class="math-container">$V_1 = S_1 \cup (S_2 \oplus m)$</span> and <span class="math-container">$V_2 = S_2 \cup (S_1 \oplus m)$</span>. Then the second term of the objective is <span class="math-container">$0$</span>, while the first term is positive.</p>

CC BY-SA 4.0
2022-05-31T12:13:58.867Z
Hi, thanks for your answer! I find the idea interesting but I have some confusion. The answer shows that if the equal subset sum problem (B) has a solution, our problem (A) may achieve the optimal (not guarantee), demonstrating the difficulty of our problem. However, if I am not wrong, if we want to show our problem (A) is NP-hard, we need to say if we can solve A then we can solve B (B is NP-hard). 
Thus, how can we show that if we can solve A, we can solve B as well?
Refrain
CC BY-SA 4.0
2022-06-07T12:07:36.623Z
Consider a case where we can solve the problem (A)(in polynomial time). Given (B) with any instance, reduce it to (A) (in polynomial time). Now solve (A). If the optimal objective value exceeds 0, it means that there are two subsets that satisfy the condition of (B). If the optimal objective function value is 0, it means that there are no such subsets. Therefore, the answer to (B) can be provided through the result of solving (A).
Seho Yim
CC BY-SA 4.0
2022-05-25T09:00:18.227Z
2022-05-25T11:57:01.447Z
2022-05-25T11:57:01.447Z
Seho Yim
<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 and a transfer matrix <span class="math-container">$\mathbf{W}\in \mathbb{R}^{d_1\times d}$</span>, 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 while minminzing the distance after transformation as follows:</p>
<p><span class="math-container">$$\max_{V_1,V_2} \hspace{1.5mm} \left(\bigg\|\frac{1}{|V_1|}\sum_{v_j \in V_1}{v_j}-\frac{1}{|V_2|}\sum_{v_k\in V_2}{v_k}\bigg\|_2-\lambda \cdot \bigg\|\frac{1}{|V_1|}\sum_{v_j \in V_1}{\mathbf{W}v_j}-\frac{1}{|V_2|}\sum_{v_k\in V_2}{\mathbf{W}v_k}\bigg\|_2\right)$$</span></p>
<p>where <span class="math-container">$\lambda&gt;0$</span> is a constant. <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> can have overlap or not.</p>
<p>How can we show its complexity? In the single objective optimization problem, we can prove its np-hardness. But could we prove this multi-objective optimization problem is np-hard or use other method to show that it is hard enough?</p>
<p>Thanks!</p>

<cc.complexity-theory><np-hardness><approximation-algorithms>
The Complexity of Multi-Objective Optimization
Refrain
# The Complexity of Multi-Objective Optimization

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

Given a vector set $V=\{v\_i\}\_{i=1}^n$ with $n$ vectors where $v\_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d\_1\times d}$, 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 while minminzing the distance after transformation as follows:

$$\max\_{V\_1,V\_2} \hspace{1.5mm} \left(\bigg\|\frac{1}{|V\_1|}\sum\_{v\_j \in V\_1}{v\_j}-\frac{1}{|V\_2|}\sum\_{v\_k\in V\_2}{v\_k}\bigg\|\_2-\lambda \cdot \bigg\|\frac{1}{|V\_1|}\sum\_{v\_j \in V\_1}{\mathbf{W}v\_j}-\frac{1}{|V\_2|}\sum\_{v\_k\in V\_2}{\mathbf{W}v\_k}\bigg\|\_2\right)$$

where $\lambda>0$ is a constant. $V\_1$ and $V\_2$ can have overlap or not.

How can we show its complexity? In the single objective optimization problem, we can prove its np-hardness. But could we prove this multi-objective optimization problem is np-hard or use other method to show that it is hard enough?

Thanks!

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms

---

## 1 answers

### Answer by username_1 on 2022-05-25. Score: 1

This problem is indeed a single objective optimization problem in the case of $W=0$.(the second term become zero) If the problem is NP-hard in the single objective case, then it is also NP-hard in the multi-objective case.

=========================================

Edit : I saw your question in the following link for the single-objective optimization version and it is in P.

[Complexity of the distance between the average vector of two subsets](https://cstheory.stackexchange.com/questions/51475/complexity-of-the-distance-between-the-average-vector-of-two-subsets)

However the problem is still NP-hard, can be reduced from the Equal Sum Subset problem which is known to be NP-hard.

In this problem, we are given a set of positive integers and we ask for two disjoint subset with equal sum of elements.

Let given instance of the Equal Sum Subset problem (B) be $\{a\_1,\cdots,a\_m\}$.

Let $\lambda = 1$, $n=2m$, $d=m+1$. Each $v\_i$ is a standard basis $e\_i$ for $i=1,\cdots,n$. This make us possible to arbitrarily set the value of $Wv\_i$. Let $M> n^2$ be a sufficiently large number.

The first $m$ coordinate of $Wv\_i$ is $Me\_i$ for $1 \le i \le m$ and $Me\_{i-m}$ for $m+1 \le i \le 2m$.

The last coordinate of $Wv\_i$ is $Ma\_i$ for $1 \le i \le m$ and $0$ otherwise.

My claim is that the multi-objective problem (A) has positive optimal value if and only if the answer of the Equal Sum Subset problem is 'yes'.

Let's make some observations. Let the optimal subsets be $V\_1^\*$ and $V\_2^\*$.

First, note that if both subset $V\_1$ and $V\_2$ are empty, the objective value is $0$.

Second, the first term of A is at most $1$.(from the single-objective case)

Third, if $v\_i \in V\_1^\*$($V\_2^\*$, respectively) for some $1 \le i \le m$, $v\_{m+i}$ must in $V\_2^\*$($V\_1^\*$, respectively). The converse is also true. Otherwise, the absolute value of the $i$th coordinate of the vector in the second term is larger than $M/n^2 > 1$ and in this case the objective value must be negative. This implies $|V\_1| = |V\_2|$.

Fourth, Let $V\_i^\* \cap [1,n] = S\_i$ for $i=1,2$. Following the third observation, the last coordinate of the vector in the second term is $0$ if $|S\_1|=0$, and $M\frac{|\sum\_{i \in S\_1}a\_i - \sum\_{j \in S\_2}a\_j |}{|S\_1|}$ otherwise.

If the answer of (B) is no, the absolute value of the last coordinate of the vector in the second term is at least $M/m > 1$ if $|S\_1| > 0$, hence the optimal value is $0$.

If the answer of the (B) is yes, let the corresponding index set of the two set be $S\_1$ and $S\_2$. Let $V\_1 = S\_1 \cup (S\_2 \oplus m)$ and $V\_2 = S\_2 \cup (S\_1 \oplus m)$. Then the second term of the objective is $0$, while the first term is positive.

> **Comments:**
> **username_0**: Hi, thanks for your answer! I find the idea interesting but I have some confusion. The answer shows that if the equal subset sum problem (B) has a solution, our problem (A) may achieve the optimal (not guarantee), demonstrating the difficulty of our problem. However, if I am not wrong, if we want to show our problem (A) is NP-hard, we need to say if we can solve A then we can solve B (B is NP-hard).  Thus, how can we show that if we can solve A, we can solve B as well?  
> **username_1**: Consider a case where we can solve the problem (A)(in polynomial time). Given (B) with any instance, reduce it to (A) (in polynomial time). Now solve (A). If the optimal objective value exceeds 0, it means that there are two subsets that satisfy the condition of (B). If the optimal objective function value is 0, it means that there are no such subsets. Therefore, the answer to (B) can be provided through the result of solving (A).  

---

