  We consider the online bipartite matching problem on $(k,d)$-bounded graphs,
where each online vertex has at most $d$ neighbors, each offline vertex has at
least $k$ neighbors, and $k\geq d\geq 2$. The model of $(k,d)$-bounded graphs
is proposed by Naor and Wajc (EC 2015 and TEAC 2018) to model the online
advertising applications in which offline advertisers are interested in a large
number of ad slots, while each online ad slot is interesting to a small number
of advertisers. They proposed deterministic and randomized algorithms with a
competitive ratio of $1 - (1-1/d)^k$ for the problem, and show that the
competitive ratio is optimal for deterministic algorithms. They also raised the
open questions of whether strictly better competitive ratios can be achieved
using randomized algorithms, for both the adversarial and stochastic arrival
models. In this paper we answer both of their open problems affirmatively. For
the adversarial arrival model, we propose a randomized algorithm with
competitive ratio $1 - (1-1/d)^k + \Omega(d^{-4}\cdot e^{-\frac{k}{d}})$ for
all $k\geq d\geq 2$. We also consider the stochastic model and show that even
better competitive ratios can be achieved. We show that for all $k\geq d\geq
2$, the competitive ratio is always at least $0.8237$. We further consider the
$b$-matching problem when each offline vertex can be matched at most $b$ times,
and provide several competitive ratio lower bounds for the adversarial and
stochastic model.
