3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ How much time is too much? I think even a linear programming solver would have no problem with that size instance. $\endgroup$
    – Austin Buchanan
    Oct 16, 2013 at 19:03
  • 1
    $\begingroup$ 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? $\endgroup$
    – iampat
    Oct 16, 2013 at 19:14
  • 6
    $\begingroup$ See the paper and references there in. arxiv.org/abs/1112.0790 $\endgroup$
    – Chandra Chekuri
    Oct 16, 2013 at 20:06

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.