Approximating the maximum weight matching problem using the GraphBLAS standard

Abstract

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.