DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.141

Online Steiner Forest with Recourse

Authors: Yaowei Long, Sepideh Mahabadi, Sherry Sarkar, and Jakub Tarnawski

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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 Θ(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.

Cite as

Yaowei Long, Sepideh Mahabadi, Sherry Sarkar, and Jakub Tarnawski. Online Steiner Forest with Recourse. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 141:1-141:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{long_et_al:LIPIcs.ICALP.2026.141,
  author =	{Long, Yaowei and Mahabadi, Sepideh and Sarkar, Sherry and Tarnawski, Jakub},
  title =	{{Online Steiner Forest with Recourse}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{141:1--141:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.141},
  URN =		{urn:nbn:de:0030-drops-265303},
  doi =		{10.4230/LIPIcs.ICALP.2026.141},
  annote =	{Keywords: Online algorithms with recourse, Steiner forest, Network design}
}

Search Results

Documents authored by Sarkar, Sherry

Online Steiner Forest with Recourse

Abstract

Cite as

Thanks for your feedback!

Could not send message