Generalized assignment problem
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other.
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.
Contents
- 1 In special cases
- 2 Explanation of definition
- 3 Complexity
- 4 Greedy approximation algorithm
- 5 See also
- 6 References
- 7 Further reading
In special cases
edit edit sourceIn 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.
Explanation of definition
edit edit sourceIn the following, we have n kinds of items, a1 through an and m kinds of bins b1 through bm. Each bin bi is associated with a budget ti. For a bin bi, each item aj has a profit pij and a weight wij. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin bi the total weight of assigned items is at most ti. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.
Mathematically the generalized assignment problem can be formulated as an integer program:
- maximize ∑i=1m∑j=1npijxij.subject to ∑j=1nwijxij≤tii=1,…,m;∑i=1mxij≤1j=1,…,n;xij∈{0,1}i=1,…,m,j=1,…,n;
Complexity
edit edit sourceThe generalized assignment problem is NP-hard.[1] However, there are linear-programming relaxations which give a (1−1/e)-approximation.[2]
Greedy approximation algorithm
edit edit sourceFor the problem variant in which not every item must be assigned to a bin, there is a family of algorithms for solving the GAP by using a combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for the GAP.[3]
Using any α-approximation algorithm ALG for the knapsack problem, it is possible to construct a (α+1)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept. The algorithm constructs a schedule in iterations, where during iteration j a tentative selection of items to bin bj is selected. The selection for bin bj might change as items might be reselected in a later iteration for other bins. The residual profit of an item xi for bin bj is pij if xi is not selected for any other bin or pij – pik if xi is selected for bin bk.
Formally: We use a vector T to indicate the tentative schedule during the algorithm. Specifically, T[i]=j means the item xi is scheduled on bin bj and T[i]=−1 means that item xi is not scheduled. The residual profit in iteration j is denoted by Pj, where Pj[i]=pij if item xi is not scheduled (i.e. T[i]=−1) and Pj[i]=pij−pik if item xi is scheduled on bin bk (i.e. T[i]=k).
Formally:
- Set T[i]=−1 for i=1…n
- For j=1,…,m do:
- Call ALG to find a solution to bin bj using the residual profit function Pj. Denote the selected items by Sj.
- Update T using Sj, i.e., T[i]=j for all i∈Sj.
See also
edit edit sourceReferences
edit edit source- ^ Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Bees algorithm for generalized assignment problem, Applied Mathematics and Computation, vol. 215, Elsevier, pp. 3782–3795, doi:10.1016/j.amc.2009.11.018. Wikipedia revision 1249232303, retrieved 2026-11-20
- ^ Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). Tight approximation algorithms for maximum general assignment problems. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp. 611–620. Wikipedia revision 1249232303, retrieved 2026-11-20
- ^ Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "An efficient approximation for the Generalized Assignment Problem". Information Processing Letters. 100 (4): 162–166. CiteSeerX 10.1.1.159.1947. doi:10.1016/j.ipl.2006.06.003.
{{cite journal}}: Cite uses deprecated parameter|citeseerx=(help) Wikipedia revision 1249232303, retrieved 2026-11-20
Further reading
edit edit source- Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2013-03-19). Knapsack Problems. Springer. ISBN 978-3-540-24777-7.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1249232303 under CC BY-SA 4.0; modifications have been made.