# Modifying sets to minimize the distance among each pair of the mean value of sets

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?

• What is a "point" to you? Jul 6 at 16:53
• @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. Jul 6 at 17:24
• OK, let me rephrase it. Are you working with Euclidean spaces? Jul 6 at 17:40
• yes, we are working with Euclidean spaces. Thanks for your help Jul 6 at 18:10
• Writing $x_i \in \Bbb R^d$ does not take too much time. Jul 6 at 18:14