Generalized assignment problem

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

In its most general form, the problem 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 task assigned to it cannot exceed this budget. It is required to find an assignment in which an agent does not exceed its budget and total profit of the assignment is maximized.

Special cases

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the maximum assignment problem. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

Definition

In the following, we have n kinds of items, ${\displaystyle x_{1}}$  through ${\displaystyle x_{n}}$  and m kinds of bins ${\displaystyle b_{1}}$  through ${\displaystyle b_{m}}$ . Each bin ${\displaystyle b_{1}}$  is associated with a budget ${\displaystyle w_{i}}$ . Each item ${\displaystyle x_{j}}$  has a value ${\displaystyle p_{ij}}$  and a weight ${\displaystyle w_{ij}}$ . 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 ${\displaystyle b_{i}}$  the weights sum of assigned items is at most ${\displaystyle w_{i}}$ . 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 (${\displaystyle {\frac {e}{e-1}}-\epsilon }$ ) hard to approximate for every ${\displaystyle \epsilon }$ .

Using any ${\displaystyle \alpha }$ -approximation algorithm for the knapsack problem, it is possible to construct a (${\displaystyle \alpha +1}$ )-approximation for the generalized assignment problem in a greedy manner using a residual profit concept. The residual profit of an item ${\displaystyle x_{i}}$  for bin ${\displaystyle b_{j}}$  is ${\displaystyle p_{ij}}$  is ${\displaystyle x_{i}}$  is not selected for any other bin or Failed to parse (syntax error): {\displaystyle p_{ij} – p_{ik} } if ${\displaystyle x_{i}}$  is selected for bin ${\displaystyle b_{k}}$ .

Formally:

For ${\displaystyle j=1...m}$  do:

find the optimal solution to bin ${\displaystyle b_{j}}$  using the residual profit function.