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?

  • $\begingroup$ 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)? $\endgroup$ – hardmath Dec 18 '16 at 15:51
  • $\begingroup$ Knspsack and set cover are possible, but there are still something wrong with the reduction process. $\endgroup$ – Steve Yang Dec 19 '16 at 2:56
  • $\begingroup$ 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$$ $\endgroup$ – hardmath Dec 19 '16 at 3:04
  • $\begingroup$ These are the values that are associated with users, and are fixed constant. $\endgroup$ – 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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.