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.net Feb 26 '14 at 18:36

This question came from our site for professional mathematicians.


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.

  • $\begingroup$ 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. $\endgroup$ – choeger Feb 26 '14 at 19:22
  • $\begingroup$ @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? $\endgroup$ – Erick Wong Feb 26 '14 at 20:33
  • $\begingroup$ 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. $\endgroup$ – choeger Feb 26 '14 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.