Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

Susanne Albers, Sebastian Schubert

We study the $b$-matching problem in bipartite graphs $G=(S,R,E)$. Each vertex $s\in S$ is a server with individual capacity $b_s$. The vertices $r\in R$ are requests that arrive o…