Optimal Competitive Ratio of Two-sided Online Bipartite Matching
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912915463864320 |
|---|---|
| author | Tang, Zhihao Gavin |
| author_facet | Tang, Zhihao Gavin |
| contents | We establish an optimal upper bound (negative result) of $\sim 0.526$ on the competitive ratio of the fractional version of online bipartite matching with two-sided vertex arrivals, matching the lower bound (positive result) achieved by Wang and Wong (ICALP 2015), and Tang and Zhang (EC 2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18049 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Competitive Ratio of Two-sided Online Bipartite Matching Tang, Zhihao Gavin Data Structures and Algorithms Computer Science and Game Theory We establish an optimal upper bound (negative result) of $\sim 0.526$ on the competitive ratio of the fractional version of online bipartite matching with two-sided vertex arrivals, matching the lower bound (positive result) achieved by Wang and Wong (ICALP 2015), and Tang and Zhang (EC 2024). |
| title | Optimal Competitive Ratio of Two-sided Online Bipartite Matching |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.18049 |