Approximate Bipartite $b$-Matching using Multiplicative Auction

Abstract

Given a bipartite graph $G(V=(A\cup B),E)$ with $n$ vertices and $m$ edges and a function $b:V\to {\mathbb{Z}}_{+}$, a $b$-matching is a subset of edges such that every vertex $v\in V$ is incident to at most $b(v)$ edges in the subset. When we are also given edge weights, the Max Weight $b$-Matching problem is to find a $b$-matching of maximum weight, which is a fundamental combinatorial optimization problem with many applications. Extending on the recent work of Zheng and Henzinger (IPCO, 2023) on standard bipartite matching problems, we develop a simple auction algorithm to approximately solve Max Weight $b$-Matching. Specifically, we present a multiplicative auction algorithm that gives a $(1-\epsilon )$-approximation in $O(m{\epsilon }^{-1}\log {\epsilon }^{-1}\log \beta )$ worst case time, where $\beta$ the maximum $b$-value. Although this is a $\log \beta$ factor greater than the current best approximation algorithm by Huang and Pettie (Algorithmica, 2022), it is considerably simpler to present, analyze, and implement.

14 pages; Accepted as a refereed paper in the 2024 INFORMS Optimization Society conference