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}$$


$$\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?

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

Your Answer

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

Browse other questions tagged or ask your own question.