Approximating the maximum weight matching problem using the GraphBLAS standard
Summary
The maximum weight matching problem for general graphs is a well-studied problem with a
variety of approximation algorithms already existing. Yet, many of them are hard to parallelize.
Therefore, we propose a 3/4-approximation algorithm completely built on matrix operations in
GraphBLAS. The idea is that these operations are more straightforward to parallelize. The algorithm is based on finding and flipping positive-gain augmentations.