Tree Coloring: Random Order and Predictions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910461027418112 |
|---|---|
| author | Frei, Fabian Gehnen, Matthias Komm, Dennis Královič, Rastislav Královič, Richard Rossmanith, Peter Stocker, Moritz |
| author_facet | Frei, Fabian Gehnen, Matthias Komm, Dennis Královič, Rastislav Královič, Richard Rossmanith, Peter Stocker, Moritz |
| contents | Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which are trivially two-colorable, it is impossible to achieve anything better than a logarithmic competitive ratio.
We show how to undercut this bound by a double-logarithmic factor in the slightly relaxed online model where the vertices arrive in random order. We then also analyze algorithms with predictions, showing how well we can color trees with machine-learned advice of varying reliability. We further extend our analysis to all two-colorable graphs and provide matching lower bounds in both cases. Finally, we demonstrate how the two mentioned approaches, both of which diminish the often unjustified pessimism of the classical online model, can be combined to yield even better results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18151 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tree Coloring: Random Order and Predictions Frei, Fabian Gehnen, Matthias Komm, Dennis Královič, Rastislav Královič, Richard Rossmanith, Peter Stocker, Moritz Data Structures and Algorithms Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which are trivially two-colorable, it is impossible to achieve anything better than a logarithmic competitive ratio. We show how to undercut this bound by a double-logarithmic factor in the slightly relaxed online model where the vertices arrive in random order. We then also analyze algorithms with predictions, showing how well we can color trees with machine-learned advice of varying reliability. We further extend our analysis to all two-colorable graphs and provide matching lower bounds in both cases. Finally, we demonstrate how the two mentioned approaches, both of which diminish the often unjustified pessimism of the classical online model, can be combined to yield even better results. |
| title | Tree Coloring: Random Order and Predictions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.18151 |