Online Steiner Forest with Recourse

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.