<p>There are still issues with the formatting, so here's an attempt to re-interpret your problem.</p>

<p>Given</p>

<ol>
<li>A collection <span class="math-container">$\mathcal{C} = \{C_1, C_2, C_3, \cdots, C_m\}$</span> of sets of points from some universe <span class="math-container">$U$</span>.</li>
<li>A similarity function <span class="math-container">$w: (U \times U) \rightarrow \mathbb{R}_0^+$</span> (or some similar codomain). Presumably this function is symmetric and nonnegative.</li>
</ol>

<p>Find a collection, <span class="math-container">$R$</span>, of points <span class="math-container">$r_1 \in C_1, r_2 \in C_2, \cdots, r_m \in C_m$</span> so to maximize the value of <span class="math-container">$$V(R) = \textrm{Repr}(R) + \textrm{Div}(R)$$</span></p>

<p>where</p>

<p><span class="math-container">$$\textrm{Repr}(R) := \sum_{i \in 1..m} \tfrac{\sum_{r' \in C_i} w(r', r_i)}{|C_i|-1}$$</span>
and
<span class="math-container">$$\textrm{Div}(R) := \dfrac{1}{2}\sum_{\stackrel{(i,j) \in (R \times R)}{i \neq j}} (1 - w(r_i, r_j))$$</span></p>

<p>This problem is NP-hard even when the range of <span class="math-container">$w$</span> is restricted to <span class="math-container">$\{0,1\}$</span>. For example, here's one reduction from <span class="math-container">$k$</span>-Independent Set. The same technique, with very little modification, can also be used to show hardness when the range of <span class="math-container">$w$</span> is limited to <span class="math-container">$\{\epsilon, 1\}$</span> for some sufficiently small <span class="math-container">$\epsilon$</span>.</p>

<p>Given a graph <span class="math-container">$G = (V,E)$</span> and an integer <span class="math-container">$k$</span>, construct <span class="math-container">$\mathcal{C}$</span> so that each <span class="math-container">$C_i$</span> contains an independent copy of <span class="math-container">$V$</span>. For any two points <span class="math-container">$a$</span> and <span class="math-container">$b$</span> in the same cluster, set <span class="math-container">$w(a, b) = 0$</span>. For any two points <span class="math-container">$a$</span>, <span class="math-container">$b$</span> in different clusters, set <span class="math-container">$w(a, b)$</span> to <span class="math-container">$1$</span> if the corresponding vertices are either neighbors in <span class="math-container">$G$</span> or correspond to the same vertex, and <span class="math-container">$0$</span> otherwise.</p>

<p>For any choice of <span class="math-container">$R$</span>, <span class="math-container">$\textrm{Repr}(R)$</span> is going to be <span class="math-container">$0$</span>, so the problem is just that of maximizing <span class="math-container">$\textrm{Div}(R)$</span>. If <span class="math-container">$G$</span> contains a <span class="math-container">$k$</span>-Independent Set, then choosing one distinct vertex from that independent set for each <span class="math-container">$C_i$</span> means that each term in the <span class="math-container">$\textrm{Div}$</span> summation is exactly <span class="math-container">$1$</span> (the maximum possible), so <span class="math-container">$\textrm{Div}(R) = {m \choose 2}$</span>. If <span class="math-container">$G$</span> does not contain a <span class="math-container">$k$</span>-Independent Set, then some pair <span class="math-container">$r_i, r_j \in (R \times R)$</span> must correspond either to the same vertex in <span class="math-container">$G$</span>, or to two neighboring vertices. In either case, the contribution of the corresponding term in the summation for <span class="math-container">$\textrm{Div}$</span> is <span class="math-container">$0$</span>, so <span class="math-container">$\textrm{Div}(R) &lt; {m \choose 2}$</span>.</p>

<p>The same reduction, with little change, can be used to get a pretty strong hardness of approximation result for your problem.</p>

CC BY-SA 4.0
2020-02-13T20:27:32.257Z
Hi, I read your answer again and again. I find I do not understand it ..How do reduce the graph to the our problem?
Refrain
CC BY-SA 4.0
2020-02-13T20:49:05.927Z
Hi, is the prove direction is wrong? should we prove the graph can be reduced to the cluster in polynomial time. However, I cannot a solution. can you give me some hints .., thanks
Refrain
CC BY-SA 4.0
2020-02-13T17:45:28.993Z
2020-02-13T17:50:35.077Z
2020-02-13T17:50:35.077Z
Yonatan N
<p>Give <span class="math-container">$n$</span> clusters <span class="math-container">$C=\{C_i\}_{i=1}^n$</span> where each cluster consists of a set of similar points, i.e., <span class="math-container">$C_i=\{c_j\}_{j=1}^{|C_i|}$</span>. The similarty between two points <span class="math-container">$c_i$</span> and <span class="math-container">$c_j$</span> is denoted as <span class="math-container">$w(c_i,c_j)$</span>. We need to select each point from each cluster as the representation of this cluster and  get the representation set <span class="math-container">$R = \{r_1,\cdots,r_n\}$</span>, which should satisfies (1) <span class="math-container">$r_i$</span> is selected from the cluster <span class="math-container">$C_i$</span> should can represent this cluster, we use the average weight of points to measure the representative score of each point <span class="math-container">$r_i$</span> in <span class="math-container">$C_i$</span>, which is defined as <span class="math-container">$r(r_i) = \frac{\sum_{r_k\in C_i}{w(r_i,r_k)}}{|C_i|-1}$</span>. Then the total representative score of points in <span class="math-container">$R$</span>  can be defined as <span class="math-container">$Repr(R)= \sum_{r_i \in R}{r(r_j)}$</span> (2) we want the representative points in <span class="math-container">$R$</span> should be diverse, and the similaritiy among
them should be large. We use the diversity score to measure them, which is defined as <span class="math-container">$Div(R)=\sum_{r_i, r_j \in}(1-w(r_i, r_j))$</span>. Hence, we want to choose a representative set <span class="math-container">$R$</span> by optimizing:</p>

<p><span class="math-container">\begin{equation}
max{(Repr(R)+ Div(R))}
\end{equation}</span></p>

CC BY-SA 4.0
2020-02-12T20:23:43.357Z
Can you clarify the problem?  What exactly is the input?  ("$n$ clusters" is not precise.)   What is the objective function that you want to optimize?  (You say that you want to maximize one function, while minimizing another.  You generally can't do both at the same time.)  What do you already know about this problem, and what have you already tried?
Neal Young
CC BY-SA 4.0
2020-02-13T02:19:02.093Z
Thanks for your suggestions! I have written it more clear. I try to use the top-k diversity problem to prove it. However, we select from clusters. It is different and I do not get the answer now.
Refrain
CC BY-SA 4.0
2020-02-13T17:35:27.027Z
(1) It seems strange to add Repr$(R)$, which is divided by cluster size, to Div$(r)$, which is not.  If all weights w(.,.) are the same order of magnitude, for inputs with large clusters Repr$(R)$ will be insignificant.  (2) Are you assuming the weights are symmetric, i.e., that $w(r_i, r_k) = w(r_k, r_i)$?
Neal Young
CC BY-SA 4.0
2020-02-13T18:43:11.517Z
Sorry for this unclear expression. (1)for the first question, you are right. But we want select a representation for each cluster. if we do not divide the size of clusters, the small size cluster will be dominated by the large size of clusters. (2) yes, it is symmetric. Thanks!
Refrain
<np-hardness><approximation-algorithms><np>
is this selection problem np-hard?
Refrain
# is this selection problem np-hard?

(Asked by: username_0 on 2020-02-12)

Give $n$ clusters $C=\{C\_i\}\_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C\_i=\{c\_j\}\_{j=1}^{|C\_i|}$. The similarty between two points $c\_i$ and $c\_j$ is denoted as $w(c\_i,c\_j)$. We need to select each point from each cluster as the representation of this cluster and get the representation set $R = \{r\_1,\cdots,r\_n\}$, which should satisfies (1) $r\_i$ is selected from the cluster $C\_i$ should can represent this cluster, we use the average weight of points to measure the representative score of each point $r\_i$ in $C\_i$, which is defined as $r(r\_i) = \frac{\sum\_{r\_k\in C\_i}{w(r\_i,r\_k)}}{|C\_i|-1}$. Then the total representative score of points in $R$ can be defined as $Repr(R)= \sum\_{r\_i \in R}{r(r\_j)}$ (2) we want the representative points in $R$ should be diverse, and the similaritiy among
them should be large. We use the diversity score to measure them, which is defined as $Div(R)=\sum\_{r\_i, r\_j \in}(1-w(r\_i, r\_j))$. Hence, we want to choose a representative set $R$ by optimizing:

\begin{equation}
max{(Repr(R)+ Div(R))}
\end{equation}

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

> **Comments:**
> **username_1**: Can you clarify the problem?  What exactly is the input?  ("$n$ clusters" is not precise.)   What is the objective function that you want to optimize?  (You say that you want to maximize one function, while minimizing another.  You generally can't do both at the same time.)  What do you already know about this problem, and what have you already tried?  
> **username_0**: Thanks for your suggestions! I have written it more clear. I try to use the top-k diversity problem to prove it. However, we select from clusters. It is different and I do not get the answer now.  
> **username_1**: (1) It seems strange to add Repr$(R)$, which is divided by cluster size, to Div$(r)$, which is not.  If all weights w(.,.) are the same order of magnitude, for inputs with large clusters Repr$(R)$ will be insignificant.  (2) Are you assuming the weights are symmetric, i.e., that $w(r_i, r_k) = w(r_k, r_i)$?  
> **username_0**: Sorry for this unclear expression. (1)for the first question, you are right. But we want select a representation for each cluster. if we do not divide the size of clusters, the small size cluster will be dominated by the large size of clusters. (2) yes, it is symmetric. Thanks!  

---

## 1 answers

### Answer by username_2 on 2020-02-13. Score: 1

There are still issues with the formatting, so here's an attempt to re-interpret your problem.

Given

1. A collection $\mathcal{C} = \{C\_1, C\_2, C\_3, \cdots, C\_m\}$ of sets of points from some universe $U$.
2. A similarity function $w: (U \times U) \rightarrow \mathbb{R}\_0^+$ (or some similar codomain). Presumably this function is symmetric and nonnegative.

Find a collection, $R$, of points $r\_1 \in C\_1, r\_2 \in C\_2, \cdots, r\_m \in C\_m$ so to maximize the value of $$V(R) = \textrm{Repr}(R) + \textrm{Div}(R)$$

where

$$\textrm{Repr}(R) := \sum\_{i \in 1..m} \tfrac{\sum\_{r' \in C\_i} w(r', r\_i)}{|C\_i|-1}$$
and
$$\textrm{Div}(R) := \dfrac{1}{2}\sum\_{\stackrel{(i,j) \in (R \times R)}{i \neq j}} (1 - w(r\_i, r\_j))$$

This problem is NP-hard even when the range of $w$ is restricted to $\{0,1\}$. For example, here's one reduction from $k$-Independent Set. The same technique, with very little modification, can also be used to show hardness when the range of $w$ is limited to $\{\epsilon, 1\}$ for some sufficiently small $\epsilon$.

Given a graph $G = (V,E)$ and an integer $k$, construct $\mathcal{C}$ so that each $C\_i$ contains an independent copy of $V$. For any two points $a$ and $b$ in the same cluster, set $w(a, b) = 0$. For any two points $a$, $b$ in different clusters, set $w(a, b)$ to $1$ if the corresponding vertices are either neighbors in $G$ or correspond to the same vertex, and $0$ otherwise.

For any choice of $R$, $\textrm{Repr}(R)$ is going to be $0$, so the problem is just that of maximizing $\textrm{Div}(R)$. If $G$ contains a $k$-Independent Set, then choosing one distinct vertex from that independent set for each $C\_i$ means that each term in the $\textrm{Div}$ summation is exactly $1$ (the maximum possible), so $\textrm{Div}(R) = {m \choose 2}$. If $G$ does not contain a $k$-Independent Set, then some pair $r\_i, r\_j \in (R \times R)$ must correspond either to the same vertex in $G$, or to two neighboring vertices. In either case, the contribution of the corresponding term in the summation for $\textrm{Div}$ is $0$, so $\textrm{Div}(R) < {m \choose 2}$.

The same reduction, with little change, can be used to get a pretty strong hardness of approximation result for your problem.

> **Comments:**
> **username_0**: Hi, I read your answer again and again. I find I do not understand it ..How do reduce the graph to the our problem?  
> **username_0**: Hi, is the prove direction is wrong? should we prove the graph can be reduced to the cluster in polynomial time. However, I cannot a solution. can you give me some hints .., thanks  

---

