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 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!

$\endgroup$

1 Answer 1

0
$\begingroup$

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

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Refrain
    May 31 at 12:13
  • $\begingroup$ 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). $\endgroup$
    – Seho Yim
    Jun 7 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.