Online Steiner Forest with Recourse
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911670059663360 |
|---|---|
| author | Long, Yaowei Mahabadi, Sepideh Sarkar, Sherry Tarnawski, Jakub |
| author_facet | Long, Yaowei Mahabadi, Sepideh Sarkar, Sherry Tarnawski, Jakub |
| contents | In the online Steiner forest problem we are given a graph $G$, and a sequence of terminal pairs $(u_i,v_i)$ which arrive in an online fashion. We are asked to maintain a low-cost subgraph in which each $u_i$ is connected to $v_i$ for all the pairs that have arrived so far. If we are not allowed to delete edges from our solution, then the best possible competitive ratio is $Θ(\log n)$. In this work, we initiate the study of low-recourse algorithms for online Steiner forest. We give an algorithm that maintains a constant-competitive solution and has an amortized recourse of $O(\log n)$, i.e., inserts and deletes $O(\log n)$ edges per demand on average. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09821 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Steiner Forest with Recourse Long, Yaowei Mahabadi, Sepideh Sarkar, Sherry Tarnawski, Jakub Data Structures and Algorithms In the online Steiner forest problem we are given a graph $G$, and a sequence of terminal pairs $(u_i,v_i)$ which arrive in an online fashion. We are asked to maintain a low-cost subgraph in which each $u_i$ is connected to $v_i$ for all the pairs that have arrived so far. If we are not allowed to delete edges from our solution, then the best possible competitive ratio is $Θ(\log n)$. In this work, we initiate the study of low-recourse algorithms for online Steiner forest. We give an algorithm that maintains a constant-competitive solution and has an amortized recourse of $O(\log n)$, i.e., inserts and deletes $O(\log n)$ edges per demand on average. |
| title | Online Steiner Forest with Recourse |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.09821 |