Generalized assignment problem: Difference between revisions

Revision as of 21:07, 22 November 2012

Revision as of 15:13, 1 December 2012

Line 3:

This problem in its most general form is as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of tasks assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

==Special cases==

Line 37:

== References ==

* Reuven Cohen, Liran Katzir, and Danny Raz, [http://www.cs.technion.ac.il/~lirank/pubs/2006-IPL-Generalized-Assignment-Problem.pdf "An Efficient Approximation for the Generalized Assignment Problem"], Information Processing Letters, Vol. 100, Issue 4, pp. 162-166 162–166, November 2006.

* Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko, [http://www-math.mit.edu/~goemans/PAPERS/ga-soda06.pdf "Tight Approximation Algorithms for Maximum General Assignment Problems"], SODA 2006, pp. 611-620 611–620.

* Hans Kellerer, Ulrich Pferschy, David Pisinger, ''Knapsack Problems '', 2005. Springer Verlag ISBN 3-540-40286-1

== External links ==

[[Category:NP-complete problems]]

[[Category:operationsNP-complete researchproblems]]

[[Category:NP-completeOperations problemsresearch]]