We revisit the online bipartite matching problem on d-regular graphs, for which Cohen and Wajc (SODA 2018) proposed an algorithm with a competitive ratio of 1-2Hd/d = 1-O ( (d) /d) and showed that it is asymptotically near-optimal for d=ω (1). However, their ratio is meaningful only for sufficiently large d, e. g. , the ratio is less than 1-1/e when d 168. In this work, we study the problem on (d, d) -bounded graphs (a slightly more general class of graphs than d-regular) and consider two classic algorithms for online matching problems: and Online Correlated Selection (OCS). We show that for every fixed d 2, the competitive ratio of OCS is at least 0. 835 and always higher than that of. When d, we show that OCS is at least 0. 897-competitive while is at most 0. 816-competitive. We also show some extensions of our results to (k, d) -bounded graphs.
Feng et al. (2025) studied this question.