@inproceedings{long2026online,
author = {Long, Yaowei and Mahabadi, Sepideh and Sarkar, Sherry and Tarnawski, Jakub},
title = {Online Steiner Forest with Recourse},
booktitle = {ICALP 2026},
year = {2026},
month = {May},
abstract = {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 $Theta(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.},
url = {http://approjects.co.za/?big=en-us/research/publication/online-steiner-forest-with-recourse/},
}