Approximate Bipartite b-Matching using Multiplicative Auction

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 ^-1) worst case time, where the maximum b-value. Although this is a factor greater than the current best approximation algorithm by Huang and Pettie (Algorithmica, 2022), it is considerably simpler to present, analyze, and implement.