<math>Insert formula here</math>The maximum general assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both task and agents have a size. Moreover, this size of each task might vary from one agent to the other. This problem
<br />
Line 12:
==Definition==
In the following, we have ''n'' kinds of items, ''x''<sub>1</sub>'' 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>.
