0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – J..y B..y
    Jul 17 at 9:43

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ what about the fact that exactly one item should be picked for all items corresponding to a particular task $\endgroup$
    – Exulansis
    Jul 5 at 7:12
  • $\begingroup$ @Exulansis, see revised answer. $\endgroup$
    – D.W.
    Jul 5 at 19:20
  • 1
    $\begingroup$ The problem admits an efficient PTAS. See the recent paper and references. drops.dagstuhl.de/opus/volltexte/2023/18101 $\endgroup$
    – Chandra Chekuri
    Jul 8 at 14:03

Your Answer

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

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