Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider using a faster solver for maximum weight matching #586

Open
smu160 opened this issue Sep 3, 2024 · 1 comment · May be fixed by #600
Open

Consider using a faster solver for maximum weight matching #586

smu160 opened this issue Sep 3, 2024 · 1 comment · May be fixed by #600

Comments

@smu160
Copy link

smu160 commented Sep 3, 2024

According to the kuhn_munkres docs, 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:

A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions.

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 Matrix included in pathfinding is perfect).

The function returns either a HashMap or a Vec of the assignments.

If this is of interest, I can create a PR with preliminary benchmarks and tests for correctness (against the current solver).

@samueltardieu
Copy link
Collaborator

samueltardieu commented Sep 3, 2024 via email

@smu160 smu160 linked a pull request Sep 16, 2024 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants