Generalized assignment 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 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.

an and m kinds of bins bi is associated with a budget aj has a profit bi the total weight of assigned items is at most (1−1/e)-approximation.

For 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.

Using any j a tentative selection of items to bin xi for bin xi is not selected for any other bin or xi is selected for bin T[i]=j means the item T[i]=−1 means that item Pj, where T[i]=−1) and bk (i.e. j=1,…,m do:

Call ALG to find a solution to bin Sj.

Update T[i]=j for all Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). Tight approximation algorithms for maximum general assignment problems. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp. 611–620.

↑