Generalized assignment problem: Difference between revisions

Content deleted Content added
m clean up using AWB
Line 1:
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:-
Line 11:
In the following, we have ''n'' kinds of items, <math>a_1</math> through <math>a_n</math> and ''m'' kinds of bins <math>b_1</math> through <math>b_m</math>. Each bin <math>b_i</math> is associated with a budget <math>t_i</math>. For a bin <math>b_i</math>, each item <math>a_j</math> has a profit <math>p_{ij}</math> and a weight <math>w_{ij}</math>. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin <math>b_i</math> the total weight of assigned items is at most <math>t_i</math>. 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_programmingInteger programming|integer program]]:
:maximize <math>\sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.</math>
:subject to <math>\sum_{j=1}^n w_{ij} x_{ij} \le t_i \qquad i=1, \ldots, m</math>;
Line 18:
 
== Complexity ==
The generalized assignment problem is [[NP-hard]],<ref>{{citation
| last1 = Özbakir | first1 = Lale
| last2 = Baykasoğlu | first2 = Adil
Line 28:
| url = http://www.sciencedirect.com/science/article/pii/S0096300309010078
| volume = 215
| 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}}
 
==Greedy approximation algorithm==
Line 48:
 
== References ==
{{Reflist}}
* 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.&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.