<p>Given <span class="math-container">$n$</span> points, each point <span class="math-container">$x_i$</span> has a value <span class="math-container">$v_i \in \mathbb{R}^{d}$</span>, and there are <span class="math-container">$m$</span> point sets <span class="math-container">$\{S_1,\dots, S_m\}$</span> that each point set consists of some points. The size of point sets can be different.  Moreover, we define the mean value of each set as</p>
<p><span class="math-container">$$v_{s_i} = \frac {1}{|S_i|} \sum_{x_j \in S_i}{v_j}$$</span></p>
<p>the target is to add or delete <span class="math-container">$k$</span> points from the <span class="math-container">$m$</span> sets. For example, we add <span class="math-container">$x_i$</span> into <span class="math-container">$S_j$</span>, which is one operation. The target is to conduct <span class="math-container">$k$</span> operations to minimize the distance</p>
<p><span class="math-container">$$\displaystyle\sum_{i=1}^m{\sum_{j=1}^m{(v_{s_i}-v_{s_j}})^2} \tag{1}$$</span></p>
<p>or</p>
<p><span class="math-container">$$\displaystyle\sum_{j=1}^m{(v_{s_i}-\bar{v}_{s}})^2 \tag{2}$$</span></p>
<p>where <span class="math-container">$\bar{v}_{s}=\frac{1}{m} \displaystyle\sum_{j=1}^m{v_{s_j}}$</span>.</p>
<p>I think that minimizing any goal of <span class="math-container">$(1)$</span> and <span class="math-container">$(2)$</span> is NP-hard, but how to prove it? Are there any approximation algorithms with a constant approximation ratio?</p>

CC BY-SA 4.0
2021-07-06T16:53:41.817Z
What is a "point" to you?
Rodrigo de Azevedo
CC BY-SA 4.0
2021-07-06T17:24:04.187Z
@Rodrigo de Azevedo hi, the point is a general description that has a unique ID, and it can be any element that has a value. In the problem, different points can have the same value, and each point can be assigned into multisets, but each point can only occur once in one set. Thanks for your attention.
Refrain
CC BY-SA 4.0
2021-07-06T17:40:34.587Z
OK, let me rephrase it.  Are you working with Euclidean spaces?
Rodrigo de Azevedo
CC BY-SA 4.0
2021-07-06T18:10:54.077Z
yes, we are working with Euclidean spaces. Thanks for your help
Refrain
CC BY-SA 4.0
2021-07-06T18:14:12.253Z
Writing $x_i \in \Bbb R^d$ does not take too much time.
Rodrigo de Azevedo
CC BY-SA 4.0
2021-07-06T19:00:43.347Z
$k$ points from each set or from all sets?
Rodrigo de Azevedo
CC BY-SA 4.0
2021-07-06T22:30:44.177Z
Please don't leave clarifications in the comments.  Instead, [edit] your question so it contains all information needed and reads well for someone who encounters it for the first time, then flag comments as 'no longer needed' once they are addressed.  Thank you!
D.W.
<np-hardness><approximation-algorithms><optimization>
Modifying sets to minimize the distance among each pair of the mean value of sets
Refrain
# Modifying sets to minimize the distance among each pair of the mean value of sets

(Asked by: username_0 on 2021-07-06)

Given $n$ points, each point $x\_i$ has a value $v\_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S\_1,\dots, S\_m\}$ that each point set consists of some points. The size of point sets can be different. Moreover, we define the mean value of each set as

$$v\_{s\_i} = \frac {1}{|S\_i|} \sum\_{x\_j \in S\_i}{v\_j}$$

the target is to add or delete $k$ points from the $m$ sets. For example, we add $x\_i$ into $S\_j$, which is one operation. The target is to conduct $k$ operations to minimize the distance

$$\displaystyle\sum\_{i=1}^m{\sum\_{j=1}^m{(v\_{s\_i}-v\_{s\_j}})^2} \tag{1}$$

or

$$\displaystyle\sum\_{j=1}^m{(v\_{s\_i}-\bar{v}\_{s}})^2 \tag{2}$$

where $\bar{v}\_{s}=\frac{1}{m} \displaystyle\sum\_{j=1}^m{v\_{s\_j}}$.

I think that minimizing any goal of $(1)$ and $(2)$ is NP-hard, but how to prove it? Are there any approximation algorithms with a constant approximation ratio?

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

> **Comments:**
> **username_1**: What is a "point" to you?  
> **username_0**: @username_1 hi, the point is a general description that has a unique ID, and it can be any element that has a value. In the problem, different points can have the same value, and each point can be assigned into multisets, but each point can only occur once in one set. Thanks for your attention.  
> **username_1**: OK, let me rephrase it.  Are you working with Euclidean spaces?  
> **username_0**: yes, we are working with Euclidean spaces. Thanks for your help  
> **username_1**: Writing $x_i \in \Bbb R^d$ does not take too much time.  
> **username_1**: $k$ points from each set or from all sets?  
> **username_2**: Please don't leave clarifications in the comments.  Instead, [edit] your question so it contains all information needed and reads well for someone who encounters it for the first time, then flag comments as 'no longer needed' once they are addressed.  Thank you!  

---

## 0 answers

