Approximate Bipartite b-Matching using Multiplicative Auction

Abstract: Given a bipartite graph G(V = (A ∪ B), E) with n vertices and m edges and a function b : V → Z+, a b-matching is a subset of edges such that every vertex v ∈ 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 − ε)-approximation in O(mε−1 log ε−1 log β) worst case time, where β the maximum b-value. Although this is a log β factor greater than the current best approximation algorithm by Huang and Pettie (Algorithmica, 2022), it is considerably simpler to present, analyze, and implement.