# Assignment problem with unique “unemployment” costs

Given $w$ workers and $k < w$ tasks, the usual integer cost matrix $(c_{ij})$ for the cost of assigning worker $i$ to task $j$ and a cost vector $(u_p)$ which assigns any selection $p$ of unassigned workers a unique unassignment cost.

We search for a minimum cost assignment where the cost includes the $u_p$ and $p$ is the vector containing all unassigned workers.

Can this problem be reformulated as an equivalent classical linear assignment problem? I.e. is there a way to model the requirement that when a worker is assigned to a task, all the combinations $p$ containing that worker may not occur in the result?

Here is a simple example: Suppose workers $a,b,c,d$ and tasks $x,y$. Assigning $a$ to $x$ and $b$ to $y$ has cost $1$, any other assignment has cost $2$. $c$ and $d$ are both in the same union, so having them both unemployed is very costly, say $u_{b,c} = 4$. Any other combination of unemployed workers cost $1$, so the minimum cost assignment has a total cost of $4$, e.g. $(a,x), (c, y)$.

edit: Whoever wants to downvote: Feel free to do so, but please be so kind to actually comment about why you downvoted.

## migrated from mathoverflow.netFeb 26 '14 at 18:36

This question came from our site for professional mathematicians.

## 1 Answer

Define $w-k$ new tasks to represent idleness. Now you can use your $c_{ij}$ formalism to model different costs of each worker being idle.

• This is not what I need. I don't have costs for every worker being unemployed but for every combination of $w-k$ unemployed workers. – choeger Feb 26 '14 at 19:22
• @choeger Are you saying that you have an exponentially-sized unemployment cost vector? In that case, it takes roughly the same time to try every combination as it does just to read the cost vector, so what's the problem? – Erick Wong Feb 26 '14 at 20:33
• Yes, that vector may be quite large. But the whole point of this exercise is to use this technique in cases where it is actually "small enough". I just want to prove the correctness of the transformation in general. – choeger Feb 26 '14 at 20:55