Optimal Online Bipartite Matching in Degree-2 Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911277306085376 |
|---|---|
| author | Bhangale, Amey Chakraborty, Arghya Harsha, Prahladh |
| author_facet | Bhangale, Amey Chakraborty, Arghya Harsha, Prahladh |
| contents | Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of $1-\frac{1}{e}$. In this work, we study classes of graphs where the online degree is restricted to $2$. As expected, one can achieve a competitive ratio of better than $1-\frac{1}{e}$ in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a $0.75$ competitive ratio algorithm is optimal. We show that the folklore \textsc{Half-Half} algorithm achieves a competitive ratio of $η\approx 0.717772\dots$ and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16025 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Online Bipartite Matching in Degree-2 Graphs Bhangale, Amey Chakraborty, Arghya Harsha, Prahladh Data Structures and Algorithms 68W20, 68R10, 90C27 Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of $1-\frac{1}{e}$. In this work, we study classes of graphs where the online degree is restricted to $2$. As expected, one can achieve a competitive ratio of better than $1-\frac{1}{e}$ in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a $0.75$ competitive ratio algorithm is optimal. We show that the folklore \textsc{Half-Half} algorithm achieves a competitive ratio of $η\approx 0.717772\dots$ and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme. |
| title | Optimal Online Bipartite Matching in Degree-2 Graphs |
| topic | Data Structures and Algorithms 68W20, 68R10, 90C27 |
| url | https://arxiv.org/abs/2511.16025 |