Paper Info
Title
A distributed-memory approximation algorithm for maximum weight perfect bipartite matching.
Abstract
Author(s): Azad, A; Buluc, A; Li, XS; Wang, X; Langguth, J | Abstract: We design and implement an efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximum weight. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization where sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64, are widely used due to the lack of scalable alternatives. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then searches for weightaugmenting cycles of length four in parallel and iteratively augments the matching with a vertex disjoint set of such cycles. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.
Year
Venue
Field
2018
arXiv: Distributed, Parallel, and Cluster Computing
Approximation algorithm,Disjoint sets,Vertex (geometry),Supercomputer,Computer science,Bipartite graph,Distributed memory,Algorithm,Matching (graph theory),Sequential algorithm,Distributed computing
DocType
Volume
Citations 
Journal
abs/1801.09809
1
PageRank 
References 
Authors
0.37
11
5
Name
Order
Citations
PageRank
Ariful Azad113815.71
Aydin Buluc2105767.49
Xiaoye S. Li3104298.22
Xinliang Wang411.38
Johannes Langguth58512.71