<p>You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess.</p>

<p><a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching" rel="nofollow">http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching</a></p>

CC BY-SA 3.0
2013-10-17T09:31:19.177Z
2013-10-17T09:31:19.177Z
Nathann Cohen
<p>I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?</p>

<p>In my problem, I have a bipartite graph with N abound 1000 (#vertices on each side) and the Hungarian algorithm takes too much time to be an option for my case.</p>

<ul>
<li>the weight on edges are real numbers but it's ok to round them to integer numbers</li>
<li>I have a brute-force greedy implementation, however, I am looking for something more sophisticated</li>
</ul>

<p>Thanks </p>

CC BY-SA 3.0
2013-10-16T19:03:01.893Z
How much time is too much? I think even a linear programming solver would have no problem with that size instance.
Austin Buchanan
CC BY-SA 3.0
2013-10-16T19:14:49.060Z
I need something in the order of 100 milliseconds or even less. Do you think it's feasible?
Do you have any suggestion for the LP solver? C++ or Python?
iampat
CC BY-SA 3.0
2013-10-16T20:06:28.707Z
See the paper and references there in. http://arxiv.org/abs/1112.0790
Chandra Chekuri
<graph-algorithms><approximation-algorithms><linear-programming><randomized-algorithms><matching>
Approximate Maximum Weight Matching
iampat
# Approximate Maximum Weight Matching

(Asked by: username_0 on 2013-10-16)

I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?

In my problem, I have a bipartite graph with N abound 1000 (#vertices on each side) and the Hungarian algorithm takes too much time to be an option for my case.

* the weight on edges are real numbers but it's ok to round them to integer numbers
* I have a brute-force greedy implementation, however, I am looking for something more sophisticated

Thanks

**Tags:** graph-algorithms, approximation-algorithms, linear-programming, randomized-algorithms, matching
> **Comments:**
> **username_1**: How much time is too much? I think even a linear programming solver would have no problem with that size instance.  
> **username_0**: I need something in the order of 100 milliseconds or even less. Do you think it's feasible? Do you have any suggestion for the LP solver? C++ or Python?  
> **username_2**: See the paper and references there in. http://arxiv.org/abs/1112.0790  

---

## 1 answers

### Answer by username_3 on 2013-10-17. Score: 3 | Accepted answer

You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess.

<http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching>


---

