# Assignment Problem — finding the $k$ agents with the best assignment

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.

• 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. – Matthew C Nov 28 '19 at 0:11
• 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$. – user89692 Nov 28 '19 at 0:14
• 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) – Matthew C Nov 28 '19 at 0:41
• (The greedy heurstic won't actually work, for instance with the matrix $[[9,2],[2,1]]$, just putting it out there) – Matthew C Nov 28 '19 at 0:42

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:
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:
The minimum cost maximum flow from $$S_1$$ to $$T$$ is the solution to the original problem for a fixed $$k$$.