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).

Improve this question
$\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, 2021 at 5:32

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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