Efficient Approximation Algorithms for Weighted $b$-Matching

Abstract

We describe a half-approximation algorithm, $b$-Suitor, for computing a $b$-Matching of maximum weight in a graph with weights on the edges. $b$-Matching is a generalization of the well-known Matching problem in graphs, where the objective is to choose a subset of $M$ edges in the graph such that at most a specified number $b(v)$ of edges in $M$ are incident on each vertex $v$. Subject to this restriction we maximize the sum of the weights of the edges in $M$. We prove that the $b$-Suitor algorithm computes the same $b$-Matching as the one obtained by the Greedy algorithm for the problem. We implement the algorithm on serial and shared-memory parallel processors and compare its performance against a collection of approximation algorithms that have been proposed earlier. Our results show that the $b$-Suitor algorithm outperforms the Greedy and locally dominant edge algorithms by one to two orders of magnitude on a serial processor. The $b$-Suitor algorithm has a high degree of concurrency, and it scales well up to 240 threads on a shared-memory multiprocessor. The $b$-Suitor algorithm outperforms the locally dominant edge algorithm by a factor of 14 on 16 cores of an Intel Xeon multiprocessor.