Generalized assignment problem: Difference between revisions

Revision as of 13:36, 26 January 2007

Revision as of 13:43, 26 January 2007

Line 11:

In the following, we have ''n'' kinds of items, <math>x_1</math> through <math>x_n</math> and ''m'' kinds of bins <math>b_1</math> through <math>b_m</math>. Each bin <math>b_1</math> is associated with a budget <math>w_i</math>. Each item <math>x_j</math> has a value <math>p_{ij}</math> and a weight <math>w_{ij}</math>. A solution is selection of items subset ''U'' and an assignment from ''U'' to the bins. A feasible solution is a solution in which for each bin <math>b_i</math> the weights sum of assigned items is at most <math>w_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.

The generalized assignment problem is NP-hard, and it is even APX-hard to approximation. Recently it was shown that it is (<math>\frac{e}{\backslash(e-1)} - \epsilon</math>) hard to approximate for every <math>\epsilon</math>.

Using any <math> \alpha</math>-approximation algorithm 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.