Generalized assignment problem: Difference between revisions

Revision as of 15:50, 9 December 2021

Latest revision as of 21:36, 3 October 2024

(7 intermediate revisions by 6 users not shown)

Line 16:

\text{maximize } & \sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}. \\

\text{subject to } & \sum_{j=1}^n w_{ij} x_{ij} \le t_i & & i=1, \ldots, m; \\

& \sum_{i=1}^m x_{ij} =\le 1 & & j=1, \ldots, n; \\

& x_{ij} \in \{0,1\} & & i=1, \ldots, m, \quad j=1, \ldots, n;

\end{align}

Line 22:

== Complexity ==

The generalized assignment problem is [[NP-hard]],.<ref>{{citation

| last1 = Özbakir | first1 = Lale

| last2 = Baykasoğlu | first2 = Adil

Line 33:

| volume = 215

| issue = 11

| year = 2010}}.</ref> However, there are linear-programming relaxations which give a <math>(1 - 1/e)</math>-approximation.<ref>{{cite journalconference |lastlast1=Fleischer |firstfirst1=Lisa |last2=Goemans |first2=Michel X. |last3=Mirrokni |first3=Vahab S. |last4=Sviridenko |first4=Maxim |date=2006 |title=Tight approximation algorithms for maximum general assignment problems |dateconference=2006Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 |pages=611–620}}</ref>

==Greedy approximation algorithm==

For 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.<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|citeseerx=10.1.1.159.1947}}</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.

Line 58:

==Further reading==

* {{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|publisher=Springer }}

[[Category:NP-complete problems]]