Generalized assignment problem: Difference between revisions

Revision as of 20:42, 25 December 2019

Latest revision as of 21:36, 3 October 2024

(13 intermediate revisions by 11 users not shown)

Line 1:

{{short description|combinatorialCombinatorial optimization problem}}

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 [[Agent-based model|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.

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.

==In special cases==

Line 18 ⟶ 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 24 ⟶ 22:

== Complexity ==

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

| last1 = Özbakir | first1 = Lale

| last2 = Baykasoğlu | first2 = Adil

Line 32 ⟶ 30:

| series = Applied Mathematics and Computation

| title = Bees algorithm for generalized assignment problem

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

| volume = 215

| issue = 11

There | isyear = 2010}}.</ref> However, there are linear-programming relaxation algorithmrelaxations which givesgive 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>

| 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==

ThereFor 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 62 ⟶ 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 }}

==External links==

[[Category:NP-complete problems]]

[[Category:Combinatorial optimization]]