samueltardieu
commented
1 week ago If this is of interest, I can create a PR with preliminary benchmarks and tests for correctness (against the current solver).
Sure, let's see how the benchmarks behave and how easily the code can take advantage of parallelization.
According to the
kuhn_munkresdocs, the maximum weight matching has the restriction, between two disjoint sets. With respect to maximum weight matching, this is a special case of the assignment problem:The hungarian algorithm has a complexity of $O(n^{3})$, but there are alternatives that have much better, theoretical, complexity. In addition, the hungarian algorithm is not as amenable to multi-threading and SIMD. One such alternative is Dmitri Bertseka's auction algorithm for the assignment problem.
Essentially, you can think of the vertices on the left side of a bipartite graph as agents, and the vertices on the right side are tasks. Then, you hold an auction where agents bid for tasks, and then you assign the winners to their desired task.
Note, this is not an exact algorithm for the assignment problem, whereas the hungarian algorithm will always provide an optimal solution.
With that being said, running an auction can lead to various pathological scenarios (e.g., bidding wars). The solution this algorithm utilizes is making each round of the auction increment prices by some value, $\epsilon$. In essence, with greater $\epsilon$, the more "aggressive" (i.e., quicker termination) auction. Why does this matter? Well, if you set $\epsilon < \frac{1}{n}$, where $n$ is the number of agents, then the solution will be optimal. This comes at the sacrifice of performance, but it will almost always be better than the hungarian algorithm.
The input to this function is a cost (i.e., weight) matrix -- the
Matrixincluded inpathfindingis perfect).The function returns either a
HashMapor aVecof the assignments.If this is of interest, I can create a PR with preliminary benchmarks and tests for correctness (against the current solver).