variant of assignment problem with overload penalties instead of constraints

Question

I want to assign $m$ tasks to $n$ workers where $m>n$, so as to minimize assignment costs defined by an $m \times n$ matrix $C$. That is, I want to find Boolean variables $x_{i,j}$ which minimize $$ \sum_{i=1}^m \sum_{j=1}^n C_{i,j}x_{i,j}, \\ s.t. \sum_{j=1}^n x_{i,j}=1 \text{ for all } i=1,\dots,m $$ Rather than a set of hard constraints, e.g., each worker can only perform a certain number of tasks, I instead want to penalize assigning lots of jobs to a single worker, by adding a second cost term $$\sum_{i=1}^m f(k_i)\,,$$ where $k_i$ is the number of jobs assigned to worker $i$ and $f$ is some super-linear function such as $f(x) = x^2$.

Is this problem as hard as the generalized assignment problem, i.e. NP-hard? I'm asking in the first case about $f(x) = x^2$ though also curious to know how the answer might change for other functions.

Answer 1

The complexity depends on the penalty function.

When the penalty function $f(\cdot)$ is non-decreasing and convex i.e. $0 \le f(k+1)-f(k) \le f(l+1)-f(l)$ whenever $k \le l$, then this problem can be solved in polynomial time as a minimum cost flow problem. $f(x) = x^2$ is a convex function in this sense.

Take the standard representation of the assignment problem as a flow network. Instead of adding one edge from the source vertex for each worker, add $m$ parallel edges for each worker. For $k \in [m]$, $k$'th edge for a worker has capacity $1$ and cost $f(k)-f(k-1)$. This solution works even if each worker $i \in [n]$ has different penalty function $f_i(\cdot)$.

If the penalty function is merely non-decreasing and not necessary convex, the reduction above breaks down because $k+1$'th edge could be chosen before the $k$'th edge. Indeed, the problem is NP-complete.

There is a simple reduction from the set cover problem. In the reduced problem instance, the sets correspond to the workers, and the elements correspond to the tasks: $$ C_{i,j} = \begin{cases} 0 & \text{ if } j \in S_i \\ \infty & \text{ otherwise} \end{cases} \\ f(k) = \begin{cases} 0 & \text{ if } k = 0 \\ 1 & \text{ otherwise} \end{cases} $$

The total cost of the assignment is equal to the number of workers with at least one task assigned. This is equivalent to minimizing the number of sets to cover all elements.

As additional information, the problem can be thought of as a welfare maximization problem of the congestion game. Here, each task corresponds to a player of the game, and the workers are resources. For example, see [1] for an overview of the computational complexity in related cases.

• [1]: Carol A. Meyers, Andreas S. Schulz. Complexity of welfare maximization in congestion games. Networks (2012).