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

$\endgroup$
  • 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 '13 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 '13 at 19:14
  • 6
    $\begingroup$ See the paper and references there in. arxiv.org/abs/1112.0790 $\endgroup$ – Chandra Chekuri Oct 16 '13 at 20:06
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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