Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917256628273152 |
|---|---|
| author | Pashkovich, Kanstantsin Snow, Thomas |
| author_facet | Pashkovich, Kanstantsin Snow, Thomas |
| contents | We study online algorithms for maximum cardinality matchings with edge arrivals in graphs of low degree. Buchbinder, Segev, and Tkach showed that no online algorithm for maximum cardinality fractional matchings can achieve a competitive ratio larger than $4/(9-\sqrt 5)\approx 0.5914$ even for graphs of maximum degree three. The negative result of Buchbinder et al. holds even when the graph is bipartite and edges are revealed according to vertex arrivals, i.e. once a vertex arrives, all edges are revealed that include the newly arrived vertex and one of the previously arrived vertices. In this work, we complement the negative result of Buchbinder et al. by providing an online algorithm for maximum cardinality fractional matchings with a competitive ratio at least $4/(9-\sqrt 5)\approx 0.5914$ for graphs of maximum degree three. We also demonstrate that no online algorithm for maximum cardinality integral matchings can have the competitive guarantee $0.5807$, establishing a gap between integral and fractional matchings for graphs of maximum degree three. Note that the work of Buchbinder et al. shows that for graphs of maximum degree two, there is no such gap between fractional and integral matchings, because for both of them the best achievable competitive ratio is $2/3$. Also, our results demonstrate that for graphs of maximum degree three best possible competitive ratios for fractional matchings are the same in the vertex arrival and in the edge arrival models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07355 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three Pashkovich, Kanstantsin Snow, Thomas Data Structures and Algorithms Computer Science and Game Theory We study online algorithms for maximum cardinality matchings with edge arrivals in graphs of low degree. Buchbinder, Segev, and Tkach showed that no online algorithm for maximum cardinality fractional matchings can achieve a competitive ratio larger than $4/(9-\sqrt 5)\approx 0.5914$ even for graphs of maximum degree three. The negative result of Buchbinder et al. holds even when the graph is bipartite and edges are revealed according to vertex arrivals, i.e. once a vertex arrives, all edges are revealed that include the newly arrived vertex and one of the previously arrived vertices. In this work, we complement the negative result of Buchbinder et al. by providing an online algorithm for maximum cardinality fractional matchings with a competitive ratio at least $4/(9-\sqrt 5)\approx 0.5914$ for graphs of maximum degree three. We also demonstrate that no online algorithm for maximum cardinality integral matchings can have the competitive guarantee $0.5807$, establishing a gap between integral and fractional matchings for graphs of maximum degree three. Note that the work of Buchbinder et al. shows that for graphs of maximum degree two, there is no such gap between fractional and integral matchings, because for both of them the best achievable competitive ratio is $2/3$. Also, our results demonstrate that for graphs of maximum degree three best possible competitive ratios for fractional matchings are the same in the vertex arrival and in the edge arrival models. |
| title | Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.07355 |