I need to do the maximum weight match in bipartite graphs. The nodes of each side are at the level of 10 ^ 3. The graph is globally sparse and locally dense. (I don’t know if this will give an idea. You can ignore this and see the problem as the maximum weight match in the full schedule.)
I know that KM (Kuhn-Munkres algorithm) can reach O (n ^ 3) and now it is being used. The problem is that I want to complete this task faster, and I can tolerate a controlled loss of less than 5%.
I tried the linear approximation algorithm from “Linear Time Approximation for Maximum Weight Matching” (2014), which has been proven to reach 1-epsilon in O (m / epsilon * log (1 / epsilon)). It seems good, but I implement it and find it a preform worse than KM, and sometimes its results are worse than the results of the greedy algorithm. :( (editing: a document for a general graph, but I simplify it by a bipartite graph, so the part related to color now does not matter)
So, does any of you guys know that some algorithms can practically outperform the KM algorithm? Or any papers look promising. Suggestions are welcome!
Thank you so much!