AuthorsJ. Langguth, A. Azad, A. Buluc, X. Li and X. Wang
TitleA distributed - memory parallel approximation of maximum weight perfect bipartite matching
AfilliationScientific Computing
Project(s)Meeting Exascale Computing with Source-to-Source Compilers
Publication TypeTalks, invited
Year of Publication2018
Location of TalkPacific Northwest National Laboratory, Richland, WA, USA

We discuss 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, are generally used due to the lack of scalable alternatives. To overcome this limitation, we propose a parallel distributed memory
algorithm and discuss its approximation properties.

Citation Key26376