Generalized assignment problem: Difference between revisions

Revision as of 15:07, 15 September 2019

Revision as of 20:42, 25 December 2019

Line 34:

| url = | doi = 10.1016/j.amc.2009.11.018

| volume = 215

| issue = 11

| year = 2010}}.</ref> and it is even [[APX-hard]] to approximate it. Recently it was shown that an extension of it is <math>e/(e-1) - \varepsilon</math> hard to approximate for every <math>\varepsilon</math>.{{Citation needed|date=November 2012}}

| year = 2010}}.</ref> and it is even [[APX-hard]] to approximate it.

There is linear-programming relaxation algorithm which gives a <math>(1 - 1/e)</math>-approximation.<ref>{{cite journal |last=Fleischer |first=Lisa |last2=Goemans |first2=Michel X. |last3=Mirrokni |first3=Vahab S. |last4=Sviridenko |first4=Maxim |title=Tight approximation algorithms for maximum general assignment problems |date=2006}}</ref>

==Greedy approximation algorithm==

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.<ref>{{cite journal |doi=10.1016/j.ipl.2006.06.003|title=An efficient approximation for the Generalized Assignment Problem|journal=Information Processing Letters|volume=100|issue=4|pages=162–166|year=2006|last1=Cohen|first1=Reuven|last2=Katzir|first2=Liran|last3=Raz|first3=Danny}}</ref>

Using any <math> \alpha</math>-approximation algorithm ALG for the [[knapsack problem]], it is possible to construct a (<math> \alpha+1</math>)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.

Using any <math> \alpha</math>-approximation algorithm ALG for the [[knapsack problem]], it is possible to construct a (<math> \alpha + 1</math>)-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 <math>j</math> a tentative selection of items to bin <math>b_j</math> is selected.

The selection for bin <math>b_j</math> might change as items might be reselected in a later iteration for other bins.

Line 51 ⟶ 56:

==See also==

* [[Assignment problem]]

== References ==

{{Reflistreflist}}

* Reuven Cohen, Liran Katzir, and Danny Raz, [https://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.&nbsp;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.&nbsp;611–620.

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

==Further reading==

== External links ==

{{cite book |isbn=978-3-540-24777-7|title=Knapsack Problems|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|last3=Pisinger|first3=David|date=2013-03-19}}

== External links ==

[[Category:NP-complete problems]]

[[Category:Combinatorial optimization]]