3
$\begingroup$

I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. How can we find the $k$ unique agents, who when each optimally allocated a unique task, result in a minimum total cost? Can this be related to the assignment problem? Thank you very much for any guidance or assistance.

$\endgroup$
  • $\begingroup$ The constraints $m\times n$ arbitrary and $k<n$ don't quite make sense without some additional details. Right now we could choose $k=0$ and solve the problem. $\endgroup$ – Matthew C Nov 28 '19 at 0:11
  • $\begingroup$ Thank you for your feedback. I am trying to find a general approach for any $k < n$. As you point out, when $k = 0$, and also when $k=1$ and $k=n$, the approach is trivial. But I am not sure of the approach for other values of $k$. $\endgroup$ – user89692 Nov 28 '19 at 0:14
  • $\begingroup$ Here's a greedy heuristic which is kind of slow: For $k=1$, find the smallest element in the matrix. For $k=2$, first find the smallest element in the matrix; then strike out its row and column. Then find the smallest element of the remaining matrix. Similarly for $k$ to min$(n,m)$ (I believe you need a minimum there because if $n>m$, for instance, then you won't be able to make unique assignments) $\endgroup$ – Matthew C Nov 28 '19 at 0:41
  • $\begingroup$ (The greedy heurstic won't actually work, for instance with the matrix $[[9,2],[2,1]]$, just putting it out there) $\endgroup$ – Matthew C Nov 28 '19 at 0:42
3
$\begingroup$

The assignment problem can be extended to solve this problem. The regular problem without the $k$ restriction can be solved by building a Minimum Cost Maximum Flow network is as follow: enter image description here

We have a source $S$ a sink $T$ and the corresponding bipartite graph in the middle. Note that each edge has two values $f/c$ which denote maximum flow allowed through this edge and cost of each flow unit. Now, the problem is that we want to allow at most $k$ units of flow from $S$ to $T$. To do this, just duplicate node $S$ into $S_1$ and $S_2$ and put an edge among them such that cost of each unit is 0 (no penalty) and maximum flow allowed is $k$. The new graph will look like this:

enter image description here

The minimum cost maximum flow from $S_1$ to $T$ is the solution to the original problem for a fixed $k$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for this thorough and detailed answer. I tried this out and it is painfully slow using some of the best packages for even a small cost matrix. Do you know if it is possible to frame the problem into the standard assignment problem framework? This would allow the application of fast AP solvers. Alternatively, would you know of a relaxation, approximation, or heuristic that would permit this framing? Thank you very much. $\endgroup$ – user89692 Nov 30 '19 at 0:33
  • $\begingroup$ What makes you think the solution for the min cost flow here would be an integer flow solution? $\endgroup$ – Tomer Wolberg May 2 at 0:06
  • 1
    $\begingroup$ @TomerWolberg en.wikipedia.org/wiki/… $\endgroup$ – Marcelo Fornet May 3 at 1:59

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.