# Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes).

The nodes each side are both (at most) the level of 10^3 and are usually unbalanced in size. The graph is globally sparse while locally dense. (I don't know whether this will give any insight. You may ignore this and see the problem as a maximum weight matching in a complete graph.)

To explain this more precisely, I'll give some examples:

• Example 1: 100 lefthand side nodes and 1,000 righthand side nodes, with sparse rate varying from 1.0, 0.5, 0.2, 0.1 to 0.01. By sparse rate, I mean there are at all sparse_rate * lefthand_nodes * righthand_nodes non-zero arcs.
As I need to find a maximum weight matching rather than a maximum weight perfect matching, I have to add additional 900 nodes to the lefthand side and fill the weight matrix (1000 * 1000) with zero because the common bipartite maximum weight matching algorithms I found are all prepared for perfect matching. That makes the actual sparse rate even smaller (equals 0.1 * the given sparse rate).

• Example 2: 1000 lefthand side nodes and 1000 righthand side nodes, with sparse rate varying from 1.0, 0.5, 0.2, 0.1 to 0.01.

• Example 3: (To explain locally dense) 100 lefthand side nodes (equally divided into 10 groups L_1, L_2, ..., L_10, with 10 nodes in each group) and 1000 righthand side nodes (equally divided into 10 groups R_1, R_2, R_3, ..., R_10, with 100 nodes in each group). L_i and R_j are densely connected if i == j but sparsely connected if i != j.

I know KM(Kuhn－Munkres algorithm) can achieve O(n^3) and now it is in use. The problem is that I want to do this task faster and I can tolerate controllable loss less than 5% (that is, the result sum of weight should be no less than 95% of the optimal solution).

But in my opinion, approximation algorithms seems a bad option as the greedy algorithm (sort the arcs, and choose applicable arcs to match from maximum weight to minimum weight) achieves the best result in most cases and runs very fast (and the running time is stable).

So do any of you guys know some algorithms can practically outperform the KM algorithm? Or any other papers look promising. Suggestions are welcomed!

Following are some methods I have tried:

• I have tried a linear approximation algorithm from Linear-Time Approximation for Maximum Weight Matching which is proved to achieve $O(1-\epsilon)$ in $O(m/\epsilon*\log(1/\epsilon))$ time. It seems good, but I implement it and find it preforms worse than KM in practical (for the given cases) and sometimes its results are worse than results of greedy algorithm. :(

• I have trie an algorithm called csa: An efficient cost scaling algorithm for the assignment problem. This works slightly better than KM when lefthand side nodes and righthand side nodes are balanced but significantly slower than KM when unbalanced. I think the problem may come from the huge amount of zero arcs I've added.

Thanks a lot!

EDIT 2016/09/01: More precise condition, some examples added, "locally dense" explained, some other methods tried.

• Welcome to CS.SE! Sounds like an interesting question. 1. What is your definition of "loss"? How do you measure the loss? 2. Can you explain what "globally sparse but locally dense" means? I haven't heard of the concept of "locally dense" before. 3. Can you tell us anything about the distribution of weights? I don't know whether that will help find better algorithms, but there's a chance it might be useful. – D.W. Jul 19 '16 at 6:30
• Thanks for your comment. I edited the post and explained the "loss". Locally dense just mean that some sub-matrixes are dense while the rest of the matrix is sparse. Beyond that, I do not have a clearer idea about the distribution. Sorry about that. – Kaho Chan Jul 19 '16 at 6:39
• @KahoChan No, really, what does "locally dense" mean? Sure, some sub-matrices are dense: the 1x1 submatrix corresponding to any edge, for example. – David Richerby Aug 31 '16 at 10:51
• 1. Have you tried using linear programming or ILP? Many linear programming solvers have a way to find an approximate solution (compute for a certain amount of time, and then return the best solution they've found so far). 2. We prefer that you avoid using "Stuff... EDIT: More stuff". Instead, edit the question so it reads well for someone reading it for the first time. See meta.cs.stackexchange.com/q/657/755. – D.W. Aug 31 '16 at 16:48
• Thanks for your comments, I'll edit the question to make it clearer. – Kaho Chan Sep 1 '16 at 2:11