Approximate Bipartite $b$-Matching using Multiplicative Auction
<|reference_start|>Approximate Bipartite $b$-Matching using Multiplicative Auction: Given a bipartite graph $G(V= (A \cup B),E)$ with $n$ vertices and $m$ edges and a function $b \colon 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 - \varepsilon)$-approximation in $O(m \varepsilon^{-1} \log \varepsilon^{-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.<|reference_end|>
@article{samineni2024approximate,
    title={Approximate Bipartite $b$-Matching using Multiplicative Auction},
    author={Bhargav Samineni, S M Ferdous, Mahantesh Halappanavar and Bala
  Krishnamoorthy},
    journal={arXiv preprint arXiv:2403.05781},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05781},
    primaryClass={cs.DS}
}