<p>The problem is NP-hard, by reduction from the the knapsack problem.  (<span class="math-container">$B$</span> 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.)</p>
<p>You can solve the problem in practice by formulating it as an instance of integer linear programming, and applying an off-the-shelf ILP solver.</p>

CC BY-SA 4.0
2023-07-05T07:12:04.867Z
what about the fact that exactly one item should be picked for all items corresponding to a particular task
Exulansis
CC BY-SA 4.0
2023-07-05T19:20:34.500Z
@Exulansis, see revised answer.
D.W.
CC BY-SA 4.0
2023-07-08T14:03:54.417Z
The problem admits an efficient PTAS. See the recent paper and references. https://drops.dagstuhl.de/opus/volltexte/2023/18101/
Chandra Chekuri
CC BY-SA 4.0
2023-07-04T22:07:53.593Z
2023-07-05T19:20:21.110Z
2023-07-05T19:20:21.110Z
D.W.
<p>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.</p>
<p>Is there some well known problem that I should look into for solving this? Ideally for the online version of this.</p>
<p>The Generalized assignment problem had per worker budget, in this case the budget is global.</p>

CC BY-SA 4.0
2023-07-17T09:43:31.577Z
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." https://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 https://cs.stackexchange.com/?
J.y B.y
<approximation-algorithms><randomized-algorithms><online-algorithms><scheduling>
Generalized assignment problem with overall budget
Exulansis
# Generalized assignment problem with overall budget

(Asked by: username_0 on 2023-07-04)

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.

**Tags:** approximation-algorithms, randomized-algorithms, online-algorithms, scheduling
> **Comments:**
> **username_1**: 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." https://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 https://cs.stackexchange.com/?  

---

## 1 answers

### Answer by username_2 on 2023-07-04. Score: 1

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

You can solve the problem in practice by formulating it as an instance of integer linear programming, and applying an off-the-shelf ILP solver.

> **Comments:**
> **username_0**: what about the fact that exactly one item should be picked for all items corresponding to a particular task  
> **username_2**: @Exulansis, see revised answer.  
> **username_3**: The problem admits an efficient PTAS. See the recent paper and references. https://drops.dagstuhl.de/opus/volltexte/2023/18101/  

---

