Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929562130055168 |
|---|---|
| author | Borst, Sander Eliáš, Marek Venzin, Moritz |
| author_facet | Borst, Sander Eliáš, Marek Venzin, Moritz |
| contents | We propose a $O(\log k \log n)$-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of $O(\log^2 k \log n)$ by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic $O(\log |C| \log |F|)$-competitive algorithm for non-metric facility location. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18542 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stronger adversaries grow cheaper forests: online node-weighted Steiner problems Borst, Sander Eliáš, Marek Venzin, Moritz Data Structures and Algorithms We propose a $O(\log k \log n)$-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of $O(\log^2 k \log n)$ by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic $O(\log |C| \log |F|)$-competitive algorithm for non-metric facility location. |
| title | Stronger adversaries grow cheaper forests: online node-weighted Steiner problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.18542 |