What type of study is this?

This is a Quantitative Study study.

October 5, 2025Open Access

Degree-bounded Online Bipartite Matching: OCS vs. Ranking

Key Points

OCS demonstrates a competitive ratio of at least 0.835, outperforming Ranking for every fixed degree.
As the degree increases, OCS achieves a competitive ratio of at least 0.897, while Ranking maxes at 0.816.
This analysis extends the findings to a broader category of (k,d)-bounded graphs from the original d-regular graphs.
The results indicate that existing algorithms can be adapted for better performance in degree-bounded situations.

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-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.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper