Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.00965 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912621069860864 |
|---|---|
| author | Feng, Yilong Li, Haolong Wu, Xiaowei Zhou, Shengwei |
| author_facet | Feng, Yilong Li, Haolong Wu, Xiaowei Zhou, Shengwei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00965 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Degree-bounded Online Bipartite Matching: OCS vs. Ranking Feng, Yilong Li, Haolong Wu, Xiaowei Zhou, Shengwei Data Structures and Algorithms 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. |
| title | Degree-bounded Online Bipartite Matching: OCS vs. Ranking |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.00965 |