2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26530 2026-09-05T19:46:36Z ddc:004 open_access

Online Steiner Forest with Recourse Long, Yaowei Mahabadi, Sepideh Sarkar, Sherry Tarnawski, Jakub Online algorithms with recourse Steiner forest Network design 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yaowei Long and Sepideh Mahabadi and Sherry Sarkar and Jakub Tarnawski 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.141 urn:nbn:de:0030-drops-265303 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.141 eng https://creativecommons.org/licenses/by/4.0/legalcode