A 3/4-approximation of the maximum weight matching problem using the GraphBLAS standard

Abstract

The maximum weight matching problem is a well-studied and central problem in graph theory, for which a variety of exact and approximation algorithms exist. Parallelisation of these algorithms is often hard, as it is for many graph problems. By designing an algorithm using the GraphBLAS standard, we gain easy access to parallelism in executing the sparse matrix operations that constitute the solution procedure. We propose an approximation algorithm based on searching and applying a set of positive-gain k-augmentations. In this method, searching for sets of 1-, 2- and 3-augmentations can be performed in linear time in terms of the size of the input graph. By performing a series of these searches and applying the positive-gain augmentations until none are available, we can guarantee a 3/4- approximation of the true maximum weight matching. We present several numerical results of experiments investigating the runtime of the algorithm and quality of the obtained results.