Suppose we have $k$ jobs, $J=\left\{ j_{1},\ldots j_{k}\right\}$ and $n$ agents, $A=\left\{ a_{1},\ldots a_{n}\right\} $. Each assignment has associated with it a subset of agents which can perform it, this information given by some $f:J\to2^{A}$ and each agent has a cost associated with using him given by $c:A\to\mathbb{N}$. We are looking for an assignment $g:J\to A$ ($g$ must be legal in the sense that $g\left(j\right)\in f\left(j\right)$ for all jobs) The cost function for an assignment $g$ is $\sum_{a\in Im\left(g\right)}c\left(a\right)$. So using any agent holds constant cost no matter how many assignments he ends performing.

Formulated as a decision problem, we have input $\left\langle J,A,f,c,k\right\rangle$ and the problem is deciding whether there exists a valid assignment with cost at most $k$.

The NP-hard problems I know about (i.e. Have proven myself) are



• Existence of a clique of size $k$ in an undirected graph

• Existence of Hamiltonian paths (All versions - with or without given start/end vertices, directed/undirected, path/cycle)

• Vertex cover of size $k$

• Dominating sets of size $k$

I have managed to prove reductions from the given problem to some of these, out of the hope that might give some insight for the reduction in the other way, but have not succeeded.

  • $\begingroup$ So each job is performed by one agent, but a single agent can perform many jobs, is that right?Just checking that I understand the question. If this is the case, can't we simply assign each job to the cheapest agent qualified to perform it? $\endgroup$ – saulspatz Jun 22 '18 at 16:04
  • $\begingroup$ @saulspatz Yes, this is the formulation of the problem as it was presented. But I figure we could equivalently ask for a subset of agents covering all jobs (Each job is associated with at least one agent in the subset) S.T. the sum of the cost for the agents in the subset is at most $k$ $\endgroup$ – H.Rappeport Jun 22 '18 at 16:09
  • $\begingroup$ But doesn't the greedy algorithm I described in my previous comment solve the problem? How can this be NP-complete? $\endgroup$ – saulspatz Jun 22 '18 at 16:17
  • $\begingroup$ @saulspatz I think a greedy approach will not work here. Consider two tasks and two agents. The first task can be performed by both, so we choose the cheaper one (Say $a_{1}$ with a cost of 2 and $a_{2}$ with a cost of 3) and the second task can only be performed by $a_{2}$, so we end up taking both with a cost of 5 where $a_{2}$ alone would have done. $\endgroup$ – H.Rappeport Jun 22 '18 at 16:20
  • $\begingroup$ Also, this was presented as a prove/disprove question, so I may be wrong. But I am pretty sure it is NP-complete $\endgroup$ – H.Rappeport Jun 22 '18 at 16:21

Answering my question

I ended up using SUBSET-SUM for the reduction. Observing that if we set the cost function $c=1$ for all agents, this is essentially a subset-sum problem. If someone sees a direct reduction from one of the problems on the list in the question I'd still like to see it.


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.