{"ID":2862132,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.00965","arxiv_id":"2510.00965","title":"Degree-bounded Online Bipartite Matching: OCS vs. Ranking","abstract":"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-2\\sqrt{H_d/d} = 1-O(\\sqrt{(\\log 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\\leq 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: \\Ranking and Online Correlated Selection (OCS). We show that for every fixed $d\\geq 2$, the competitive ratio of OCS is at least $0.835$ and always higher than that of \\Ranking. When $d\\to \\infty$, we show that OCS is at least $0.897$-competitive while \\Ranking is at most $0.816$-competitive. We also show some extensions of our results to $(k,d)$-bounded graphs.","short_abstract":"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-2\\sqrt{H_d/d} = 1-O(\\sqrt{(\\log d)/d})$ and showed that it is asymptotically near-optimal for $d=ω(1)$. However, their ratio is meaningful only for sufficient...","url_abs":"https://arxiv.org/abs/2510.00965","url_pdf":"https://arxiv.org/pdf/2510.00965v1","authors":"[\"Yilong Feng\",\"Haolong Li\",\"Xiaowei Wu\",\"Shengwei Zhou\"]","published":"2025-10-01T14:37:19Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}