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.
On
If all $t_i$s are $1$, then (as said in the linked post), the problem becomes a perfect matching problem. Which is easy to solve.
But here, because you take a $\max$ of a sum of costs, this would translate into a hypergraph matching (where the hyperedges are, for a worker, the groups of tasks whose sum is below the threshold), which (in general) is much harder. You can't directly prove that the hardness of general hypergraph matching translates to this problem, because you can't encode general hypergraphs as arising from this problem ; but it looks like bad news...
If the $t_i$ aren't fixed (but instead we only insist that each task is assigned exactly once), this is the Santa Claus problem (but instead of giving tasks, you give presents ! Way nicer), which is difficult but has an approximation algorithm.
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\}$.