Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
This work provides a practical improvement for computational tasks requiring efficient matching algorithms, though it is incremental as it builds on existing cherry blossom methods.
The paper tackles the minimum weight perfect matching problem by implementing an algorithm that outperforms the state-of-the-art Blossom V on instances where Blossom V takes superlinear time, achieving almost-linear runtime in practice.
We implement an algorithm for solving the minimum weight perfect matching problem. Our code significantly outperforms the current state-of-the-art Blossom V algorithm on those families of instances where Blossom V takes superlinear time. In practice, our implementation shows almost-linear runtime on every family of instances on which we have tested it. Our algorithm relies on solving the maximum-cardinality unweighted matching problems during its primal phase. Following the state-of-the-art cherry blossom algorithm, we use cherry trees instead of traditional alternating trees and cherry blossoms instead of traditional blossoms. We shrink cherry blossoms rather than traditional blossoms into supernodes. This strategy allows us to deal with much shallower supernodes.