Answers are grounded in this paper and cite their sources.
Analysis reveals that Online Correlated Selection shows a higher competitive ratio than Ranking, suggesting improved matching strategies.
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√Hd/d = 1-O(√(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≤ 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.
No takes yet. Share an insight, caveat, or question.
Feng et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: