0
$\begingroup$

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness?

The decision version of the generalized assignment problem is to determine whether there exists an assignment where every job is fulfilled (as opposed to maximizing the number of jobs that can be fulfilled).

$\endgroup$
1
  • $\begingroup$ To show NP-hardness reduce any NP-hard problem to it. Practically, you'll want to use an NP-complete problem, though. $\endgroup$
    – idmean
    Aug 1 '21 at 5:32
1
$\begingroup$

Copied from Wikipedia:

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the assignment problem. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

$\endgroup$

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.