# is this selection problem np-hard? [closed]

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:

$$$$max{(Repr(R)+ Div(R))}$$$$

• 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 Feb 12 at 20:23
• 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 Feb 13 at 2:19
• (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 Feb 13 at 17:35
• 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 Feb 13 at 18:43

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.

• 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 Feb 13 at 20:27
• 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 Feb 13 at 20:49