In the following, we have ''n'' kinds of items, ''x''<submath>1x_1</submath> through ''x''<sub>n</sub> and ''m'' kinds of bins ''b''<sub>1</sub> through ''b''<sub>m</sub>. Each bin ''b''<sub>1</sub> is associated with a budget ''w''<sub>i</sub>. Each item ''x''<sub>j</sub> has a value ''p''<sub>ij</sub> and a weight ''w''<sub>ij</sub>. 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 ''b''<sub>i</sub>. the weights sum of assigned items is at most ''w''<sub>i</sub>. 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}{e-1} - \epsilon</math>) hard to approximate for every <math>\epsilon</math>.
