# A variant of the Hungarian algorithm / assignment problem

Is there an algorithm for the following variant of the assignment problem:

Suppose we have $n$ workers $A_i$ and $m$ tasks and each worker $A_i$ has to do exactly $t_i$ tasks. (The numbers are chosen such that $m= \sum_{i=1}^n t_i$.) For any $i$ let $C_i$ be the sum of the costs of worker $A_i$. I am searching for an assignment such that $\max_i C_i$ is minimal.

I have found this variant, but this deals only with the maximal cost of one task, not with the sum of the tasks for one worker.

I would solve this problem via integer programming. Let $x_{ij}$ be decision variable for the worker $A_i$ do the task $j$ and $c_{ij}$ be the cost of worker $A_i$ do the task $j$. We have $C_i = \sum\limits_{j=1}^mc_{ij}x_{ij}$. We need to solve the following IP: $\min z$ subject to $\sum\limits_{j=1}^mx_{ij} = t_i$ and $\sum\limits_{j=1}^mc_{ij}x_{ij} \leq z$ for all $i=1,\ldots,n$, and $x_{ij}\in \{0,1\}$.