Online Steiner Forest with Recourse
This work initiates the study of low-recourse algorithms for online Steiner forest, addressing a known bottleneck in dynamic network design.
The paper studies the online Steiner forest problem with recourse, presenting an algorithm that maintains a constant-competitive solution while achieving an amortized recourse of O(log n) edges per demand.
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.