<p>You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: <a href="https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf">https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf</a> but more optimizations are possible). </p>

<p>These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so are often efficient in practice, and are amenable to parallelization. (And they can be used as a basis for recovering the best known worst case running times, see: <a href="http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/">http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/</a></p>

CC BY-SA 3.0
2014-08-12T14:18:56.340Z
2014-08-12T14:18:56.340Z
Aaron Roth
<p>I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks.</p>

<p>I have an implementation of the Hungarian Algorithm which takes about a minute to solve for my $640 \times 640$ matrix. For forbidden assignments, I set the cost to $\infty$. (There <em>always</em> exists a feasible solution in my problem).</p>

<p>I've also set it up as a binary program in CPLEX, which takes about 9 seconds to solve for the same problem. The BIP model excludes forbidden assignments outright by omitting those variables.</p>

<p>I haven't yet investigated setting it up as a networking model in CPLEX, but that will likely be my next step. There is, however, a performance cost with communicating with CPLEX, so I'm sure a dedicated algorithm should get better performance.</p>

<p>This bipartite matching problem is a kernel within another iterative search algorithm, so it must run <em>as fast as possible</em>.</p>

<p>Are there any algorithms that I can implement that will outperform the Hungarian Algorithm in this case? Or do you have any other suggestions on how I can improve the performance of this kernel?</p>

CC BY-SA 3.0
2014-08-12T12:37:57.677Z
Just as a side note, the bipartite matching is highly relevant to minimum maximum flow, and as I see seems you have a dynamic situation and your original graph maybe does not change too much in two consecutive iterations, so perhaps you can find something relevant to your work along line of this [question and answer](http://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs).
Saeed
CC BY-SA 3.0
2014-08-14T02:26:01.163Z
@Saeed, thanks, I had considered representing it as a min cost network using the information from the previous iteration as an initial feasible solution.
Ozzah
<graph-algorithms><optimization><matching>
Fast algorithm for weighted bipartite matching problem
Ozzah
# Fast algorithm for weighted bipartite matching problem

(Asked by: username_0 on 2014-08-11)

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks.

I have an implementation of the Hungarian Algorithm which takes about a minute to solve for my $640 \times 640$ matrix. For forbidden assignments, I set the cost to $\infty$. (There *always* exists a feasible solution in my problem).

I've also set it up as a binary program in CPLEX, which takes about 9 seconds to solve for the same problem. The BIP model excludes forbidden assignments outright by omitting those variables.

I haven't yet investigated setting it up as a networking model in CPLEX, but that will likely be my next step. There is, however, a performance cost with communicating with CPLEX, so I'm sure a dedicated algorithm should get better performance.

This bipartite matching problem is a kernel within another iterative search algorithm, so it must run *as fast as possible*.

Are there any algorithms that I can implement that will outperform the Hungarian Algorithm in this case? Or do you have any other suggestions on how I can improve the performance of this kernel?

**Tags:** graph-algorithms, optimization, matching

> **Comments:**
> **username_1**: Just as a side note, the bipartite matching is highly relevant to minimum maximum flow, and as I see seems you have a dynamic situation and your original graph maybe does not change too much in two consecutive iterations, so perhaps you can find something relevant to your work along line of this [question and answer](http://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs).  
> **username_0**: @username_1, thanks, I had considered representing it as a min cost network using the information from the previous iteration as an initial feasible solution.  

---

## 1 answers

### Answer by username_2 on 2014-08-12. Score: 7

You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: <https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf> but more optimizations are possible).

These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so are often efficient in practice, and are amenable to parallelization. (And they can be used as a basis for recovering the best known worst case running times, see: <http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/>


---

