Approximate Bipartite $b$-Matching using Multiplicative Auction

Bhargav Samineni, S M Ferdous, Mahantesh Halappanavar +1

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 verte…