Parallel algorithm speeds up approximate maximum-product matching in bipartite graphs

Dual-Slack Frontier Matching: Parallel Approximate Maximum-Product Matching

Data Structures and Algorithms

Summary

Finding the best way to pair items from two groups, like matching workers to jobs, is a key problem in computer science. This paper presents a new algorithm called Dual-Slack Frontier Matching (DSFM) that quickly finds nearly optimal pairings using multiple processors at once. The authors show that their method is often faster and produces better matches than previous approaches when tested on many matrices. The algorithm also provides guarantees about the quality of the matches it finds.

What this means in practice

Authors

Marc A. Tunnell, Oguz Selvitopi, Xiaoye Sherry Li

Abstract

Maximum-product bipartite matching supports scaling and static pivot selection in sparse matrix preprocessing. We present Dual-Slack Frontier Matching (DSFM), a deterministic, shared-memory parallel algorithm for approximate maximum-product matching. Motivated by heavy matchings on small candidate supports, DSFM searches progressively exposed subgraphs ordered by fixed dual slack. Slack-ordered certified completion guarantees a perfect matching whenever one exists, or a maximum-cardinality matching with a Hall certificate otherwise. Every returned perfect matching carries an a posteriori geometric-mean quality bound; accumulated Hall obstructions can tighten this bound and improve the returned scaling. We compare DSFM with Heavy-Weight Perfect Matching (HWPM) and exact MC64 assignment on 598 nonsingular matrices. DSFM attains higher matching quality than HWPM over most quality thresholds. On a set of large instances consisting of 37 matrices, DSFM achieves a $3.53\times$ geometric-mean speedup over MC64, compared to $2.29\times$ for HWPM.