1
$\begingroup$

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?

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.