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