2024/03/09 by Bhargav Samineni, Samineni, Bhargav, S M Ferdous +5
Decision Sciences · Computer Science · Business, Management and Accounting · #Auction Theory and Applications #Optimization and Search Problems #Consumer Market Behavior and Pricing
paper · pdf · doi:10.48550/arxiv.2403.05781
Given a bipartite graph G(V= (A ∪ B),E) with n vertices and m edges and a function b \colon V → ℤ+, 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.