# Generalized assignment problem with overall budget

The problem has N tasks. We have M workers. We have the cost of assigning task i to worker j. We have a profit for assigning task i to worker j. We want to assign each task to exactly one worker. One worker may be assigned multiple tasks. Given a budget B for spending on workers, what is the maximum profit I can get.

Is there some well known problem that I should look into for solving this? Ideally for the online version of this.

The Generalized assignment problem had per worker budget, in this case the budget is global.

• This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("a question and answer site for professional researchers in theoretical computer science and related fields." cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like cs.stackexchange.com? Commented Jul 17, 2023 at 9:43

The problem is NP-hard, by reduction from the the knapsack problem. ($$B$$ represents the maximum weight capacity of the knapsack, and for each item, add a new pair of task and worker with cost equal to the weight of the item and profit equal to the value of the item. Also add one more worker that is connected to all item-tasks, via edges with cost 0 and profit 0.)