# How to prove the NP-hardness or NP-completeness of this assignment problem

Here's the problem.

Suppose there are $n$ users, each with an value $\sigma_i$. There are $m$ tasks, and we want to assign each user a task. Suppose for each task $j$, the set of users assigned to it is denoted by $S_j$.

Each task has a reward $v_j$. Accomplishing each task $j$ needs to satisfy that $\frac{\sum_{i \in S_j}\sigma_i}{|S_j|^2} \leq \theta$, where $\theta$ is a fixed constant. Let $u_j \in \{0,1\}$ denote if the task $j$ is accomplished ("1" means accomplished, and "0" means not).

The objective of the problem is to find a user assignment method so as to maximize the total obtained value of tasks, that is: $$\underset{\{S_j\}}{\textrm{max}} ~~ \sum_{j=1}^m v_j* u_j$$

I'm not sure which NPC problem can be reduced to this problem. Can someone help me?

• Which problems have you been shown (in the context of this class) to be NP Complete? Of these which are possible to express as instances of the problem recounted above (through polynomial-time conversion)? – hardmath Dec 18 '16 at 15:51
• Knspsack and set cover are possible, but there are still something wrong with the reduction process. – Steve Yang Dec 19 '16 at 2:56
• What is known about the summands $\sigma_i$ that appear in your constraints: $$\frac{\sum_{i\in S_j} \sigma_i}{|S_j|^2} \le \theta$$ – hardmath Dec 19 '16 at 3:04
• These are the values that are associated with users, and are fixed constant. – Steve Yang Dec 19 '16 at 3:23

A formal formalization of the problem is: \begin{align} \textrm{max} ~~ & v_j * y_j \notag \\ \textrm{s.t.}~~ & \sum_{i=1}^n x_{i,j} \sigma_i^2 \leq \theta (\sum_{i=1}^n x_{i,j})^2, \forall j \notag \\ & \sum_{j=1}^m x_{i,j}=1, \forall j \notag \\ & y_j \in \{0,1\} \notag \\ & x_{i,j} \in \{0,1\} \notag \\ \end{align}

We can see that the problem is nonlinear integer programming, which is NP-hard.