An auction-based weighted matching implementation on massively parallel architectures

Maximum weighted matchings represent a fundamental kernel in massive graph analysis and occur in a wide range of real-life applications. Here, a parallel auction-based matching algorithm is developed, which is able to tackle matchings in very large, dense, and sparse bipartite graphs. It will be demonstrated that the convergence of the auction algorithm crucially depends on two different εε-scaling strategies. The auction algorithm including the εε-scaling strategies has been implemented using a hybrid MPI–OpenMP programming model, and its performance is validated in various applications from bioinformatics, computer vision, and sparse linear algebra. It is concluded that for dense bipartite graphs, the auction algorithm scales well, and for sparse bipartite graphs at least a substantial speedup is achieved against alternative approaches that are based on augmenting path algorithms.

► Design of a distributed-memory auction-based weighted matching algorithm.
► Using the hybrid MPI–OpenMP programming model.
► Introducing different εε-scaling strategies in the auction algorithm.
► Finding of weighted matchings in data intensive applications.
► Solving the matching problem for dense, sparse, balanced and unbalanced bipartite graphs.