  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 online and must be assigned instantly to an
eligible server. The goal is to maximize the size of the constructed matching.
We assume that $G$ is a $(k,d)$-graph~\cite{NW}, where $k$ specifies a lower
bound on the degree of each server and $d$ is an upper bound on the degree of
each request. This setting models matching problems in timely applications.
  We present tight upper and lower bounds on the performance of deterministic
online algorithms. In particular, we develop a new online algorithm via a
primal-dual analysis. The optimal competitive ratio tends to~1, for arbitrary
$k\geq d$, as the server capacities increase. Hence, nearly optimal solutions
can be computed online. Our results also hold for the vertex-weighted problem
extension, and thus for AdWords and auction problems in which each bidder
issues individual, equally valued bids.
  Our bounds improve the previous best competitive ratios. The asymptotic
competitiveness of~1 is a significant improvement over the previous factor of
$1-1/e^{k/d}$, for the interesting range where $k/d\geq 1$ is small. Recall
that $1-1/e\approx 0.63$. Matching problems that admit a competitive ratio
arbitrarily close to~1 are rare. Prior results rely on randomization or
probabilistic input models.
