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

• ludog: Thanks, great answer. I'm unsure about the use of convexity though. Stricitly speaking, only continuous functions can be convex, you seem to mean sth like superlinear. Maybe this is nitpicking, but I'm more interested in whether it really is the key property that makes the problem hard. In your set cover reduction, it feels instead like the complexity comes from multiple edges having the same penalty and the ambiguity this produces.
• pcpthm: Re: convexity, right, the property is not same as the most common definition of convexity of a function. I believe it is a common practice to define convexity for a discrete function in this way. The linked paper also uses this terminology. The property is not same as super-liner.
• pcpthm: Re: multiple edges having the same penalty, This is not essential. It doesn't change the problem if the penalty for $k > 0$ is 1ドル + \epsilon k$ for 0ドル < \epsilon \ll 1$ but now the penalty function is strictly increasing.
• ludog: I guess this works for $\epsilon < 1/m$ or something, but is this the same requirement as the convex nondecreasing property?
• ludog: the question is whether non-convexity, as you define it, is a sufficient condition for NP-completeness