arxiv: 2605.09821 · v1 · submitted 2026-05-10 · 💻 cs.DS

Recognition: 2 theorem links

· Lean Theorem

Online Steiner Forest with Recourse

Yaowei Long , Sepideh Mahabadi , Sherry Sarkar , Jakub Tarnawski

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:11 UTC · model grok-4.3

classification 💻 cs.DS

keywords online steiner forestrecoursecompetitive analysisonline algorithmsnetwork designdynamic connectivity

0 comments

The pith

The online Steiner forest problem admits a constant-competitive algorithm with amortized O(log n) recourse.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In the online Steiner forest problem, a graph is given and terminal pairs arrive one by one; the algorithm must maintain a subgraph connecting each arrived pair. Without edge deletions the best possible competitive ratio is Theta(log n). The paper gives an algorithm that achieves constant competitiveness while allowing deletions, with an amortized cost of O(log n) edge insertions and deletions per new demand. This shows that bounded recourse can replace the logarithmic barrier in online network design.

Core claim

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.

What carries the argument

An online maintenance algorithm for connectivity of terminal pairs that bounds total edge insertions and deletions across the entire sequence.

If this is right

The competitive ratio improves from Theta(log n) to a constant.
The total number of edge changes across all demands remains O(m log n) when m demands arrive.
The algorithm works in the standard online model with no knowledge of future arrivals.
Recourse allows the solution to stay close to the offline optimum while adapting gradually.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same technique may apply to other online connectivity problems such as Steiner tree or group Steiner forest.
Low amortized recourse could make constant-competitive online solutions feasible in settings where recomputation is expensive.
One could test whether the O(log n) bound is tight by constructing worst-case demand sequences that force logarithmic changes even for constant-competitive solutions.

Load-bearing premise

The input graph is undirected and the sequence of terminal pairs is presented by an adversary without knowledge of future pairs.

What would settle it

A sequence of terminal-pair arrivals on which every constant-competitive solution requires amortized recourse strictly higher than O(log n) per demand.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first constant-competitive algorithm for online Steiner forest that uses only O(log n) amortized recourse, breaking the Theta(log n) barrier from the no-deletion case.

read the letter

The main thing to know is that allowing O(log n) amortized edge insertions and deletions per arriving terminal pair lets you maintain a constant-competitive solution for online Steiner forest, where the classic no-recourse version cannot beat Theta(log n). The paper initiates this low-recourse direction and supplies the algorithm that achieves it under the standard undirected-graph, oblivious-adversary model. It does a clean job of stating the bounds and contrasting them with the prior lower bound, which is useful framing. The approach appears to adapt existing online Steiner techniques with targeted rerouting to control the total changes. The soft spots are minor at this stage: the abstract gives no proof sketch, so the charging argument or potential function that bounds recourse and competitiveness cannot be checked yet, and it is unclear how large the hidden constant in the competitiveness ratio actually is. Amortized recourse is a reasonable relaxation but leaves open whether a worst-case per-step bound is possible. The model assumptions are standard and not a weakness. This work is for people in online algorithms and network design who care about recourse models or beating classic lower bounds with limited modifications. A reader following competitive analysis for Steiner problems would get direct value from seeing the new combination of guarantees. It deserves a serious referee to verify the analysis, even if revisions are needed on the constants or presentation.

Referee Report

0 major / 3 minor

Summary. The paper studies the online Steiner forest problem on undirected graphs, where terminal pairs arrive online and the algorithm must maintain a subgraph connecting all arrived pairs. Without edge deletions the best competitive ratio is Θ(log n); the authors initiate the study of low-recourse variants and present an algorithm that maintains a constant-competitive solution while incurring an amortized O(log n) recourse (total edge insertions plus deletions per demand).

Significance. If the claimed bounds hold, the result is a meaningful advance: it shows that a modest amount of recourse suffices to improve the competitive ratio from logarithmic to constant for online Steiner forest. This opens a new direction for recourse-augmented online network design and supplies a concrete algorithmic template that may extend to related problems such as online Steiner tree or group Steiner forest.

minor comments (3)

The abstract states a constant competitive ratio but does not name the constant; stating the explicit ratio (e.g., 4 or 8) already in the abstract would strengthen the claim.
§3 (algorithm description): the high-level description of the recourse mechanism is clear, but the precise rule for when an edge is deleted versus retained during a demand update could be stated more formally, perhaps as a short pseudocode block.
The amortization argument for the O(log n) recourse bound relies on a potential function; a short paragraph summarizing the potential and how it decreases on average would make the analysis easier to follow without reading the full proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report accurately reflects the paper's contributions on constant-competitive online Steiner forest with amortized O(log n) recourse. No major comments are listed in the report, so we have no points requiring response or revision.

Circularity Check

0 steps flagged

No significant circularity; direct algorithmic claim

full rationale

The paper states an algorithmic result for the online Steiner forest problem under the standard model: a constant-competitive solution with amortized O(log n) recourse via edge insertions and deletions. The abstract presents this as a direct contribution without any equations, parameter fits, self-referential definitions, or load-bearing citations that reduce the claim to its own inputs by construction. No derivation chain is exhibited in the provided text that would allow a prediction or uniqueness result to collapse into a fitted input or prior self-citation. The result is therefore self-contained as an existence claim for an algorithm, consistent with the default expectation that most papers exhibit no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of an unspecified algorithm whose analysis yields constant competitiveness and O(log n) amortized recourse; no free parameters, axioms, or invented entities are visible in the abstract.

axioms (1)

domain assumption Standard assumptions of the online competitive-analysis model for undirected graphs
Implicit in any online Steiner-forest statement but not enumerated in the abstract.

pith-pipeline@v0.9.0 · 5423 in / 1102 out tokens · 42513 ms · 2026-05-12T02:11:04.897927+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 4.7. For each level i we have X_t |F̂(t)_i ∖ F̂(t)_inh,i| · 2^{i+1} ≤ O(OPT)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

81 extracted references · 81 canonical work pages

[1]

Space- and

Anupam Gupta and Amit Kumar , editor =. Greedy Algorithms for Steiner Forest , booktitle =. 2015 , url =. doi:10.1145/2746539.2746590 , timestamp =

work page doi:10.1145/2746539.2746590 2015
[2]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21) , pages =

Bhattacharya, Sayan and Grandoni, Fabrizio and Wajc, David , title =. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21) , pages =. 2021 , publisher =. doi:10.1137/1.9781611976465.168 , timestamp =

work page doi:10.1137/1.9781611976465.168 2021
[3]

Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA '25) , pages =

Forster, Sebastian and Skarlatos, Antonis , title =. Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA '25) , pages =. 2025 , publisher =. doi:10.1137/1.9781611978322.7 , timestamp =

work page doi:10.1137/1.9781611978322.7 2025
[4]

Proceedings of the 34th International Conference on Machine Learning (ICML 2017) , series =

Lattanzi, Silvio and Vassilvitskii, Sergei , title =. Proceedings of the 34th International Conference on Machine Learning (ICML 2017) , series =. 2017 , editor =

work page 2017
[5]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21) , pages =

Fichtenberger, Hendrik and Lattanzi, Silvio and Norouzi-Fard, Ashkan and Svensson, Ola , title =. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21) , pages =. 2021 , publisher =. doi:10.1137/1.9781611976465.158 , timestamp =

work page doi:10.1137/1.9781611976465.158 2021
[6]

Fully Dynamic Consistent k-Center Clustering , booktitle =

Jakub. Fully Dynamic Consistent k-Center Clustering , booktitle =. doi:10.1137/1.9781611977912.124 , year =

work page doi:10.1137/1.9781611977912.124
[7]

Online bipartite matching with amortized O(log2n)replacements.J

Bernstein, Aaron and Holm, Jacob and Rotenberg, Eva , title =. 2019 , issue_date =. doi:10.1145/3344999 , journal =

work page doi:10.1145/3344999 2019
[8]

2017 , isbn =

Gupta, Anupam and Krishnaswamy, Ravishankar and Kumar, Amit and Panigrahi, Debmalya , title =. 2017 , isbn =. doi:10.1145/3055399.3055493 , booktitle =

work page doi:10.1145/3055399.3055493 2017
[9]

doi:10.1145/2746539.2746615 , booktitle =

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree , year =. doi:10.1145/2746539.2746615 , booktitle =

work page doi:10.1145/2746539.2746615
[10]

Proceedings of the 2022

Anupam Gupta and Vijaykrishna Gurunathan and Ravishankar Krishnaswamy and Amit Kumar and Sahil Singla , title =. Proceedings of the 2022. 2022 , pages =. doi:10.1137/1.9781611977073.57 , url =

work page doi:10.1137/1.9781611977073.57 2022
[11]

Symmetry Exploitation for Online Machine Covering with Bounded Migration , year =

Waldo G. Symmetry Exploitation for Online Machine Covering with Bounded Migration , year =. doi:10.1145/3397535 , journal =

work page doi:10.1145/3397535
[12]

SIAM Journal on Discrete Mathematics , volume =

de Berg, Mark and Sadhukhan, Arpan and Spieksma, Frits , title =. SIAM Journal on Discrete Mathematics , volume =. 2024 , doi =

work page 2024
[13]

Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics , pages =

Consistent Online Optimization: Convex and Submodular , author =. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics , pages =. 2019 , editor =

work page 2019
[14]

Approximation, Randomization, and Combinatorial Optimization

Megow, Nicole and N\". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.37 , annote =

work page doi:10.4230/lipics.approx/random.2020.37 2020
[15]

and Li, Jerry and Liu, Allen and Narayanan, Shyam , booktitle =

Bhattacharya, Sayan and Buchbinder, Niv and Levin, Roie and Saranurak, Thatchaphol , booktitle =. Chasing Positive Bodies , year =. doi:10.1109/FOCS57990.2023.00103 , timestamp =

work page doi:10.1109/focs57990.2023.00103 2023
[16]

Changing Bases: Multistage Optimization for Matroids and Matchings , booktitle =

Anupam Gupta and Kunal Talwar and Udi Wieder , editor =. Changing Bases: Multistage Optimization for Matroids and Matchings , booktitle =. 2014 , url =. doi:10.1007/978-3-662-43948-7_47 , timestamp =

work page doi:10.1007/978-3-662-43948-7_47 2014
[17]

Sujoy Bhore and Arnold Filtser and Csaba D. T. Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings , booktitle =. 2024 , pages =. doi:10.1137/1.9781611977912.162 , url =

work page doi:10.1137/1.9781611977912.162 2024
[18]

The Power of Recourse for Online

Nicole Megow and Martin Skutella and Jos. The Power of Recourse for Online. Automata, Languages, and Programming - 39th International Colloquium,. 2012 , url =. doi:10.1007/978-3-642-31594-7_58 , timestamp =

work page doi:10.1007/978-3-642-31594-7_58 2012
[19]

Online knapsack with removal and recourse , journal =

Hans-Joachim Böckenhauer and Ralf Klasing and Tobias Mömke and Peter Rossmanith and Moritz Stocker and David Wehner , timestamp =. Online knapsack with removal and recourse , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.jcss.2025.103697 , url =

work page doi:10.1016/j.jcss.2025.103697 2026
[20]

Karp.Reducibility among Combinatorial Problems, pages 85–103

Richard M. Karp , editor =. Reducibility Among Combinatorial Problems , booktitle =. 1972 , timestamp =. doi:10.1007/978-1-4684-2001-2_9 , _bib2doi_selected =

work page doi:10.1007/978-1-4684-2001-2_9 1972
[21]

Theoretical Computer Science , volume =

The Steiner tree problem on graphs: Inapproximability results , author =. Theoretical Computer Science , volume =. 2008 , publisher =. doi:10.1016/j.tcs.2008.06.046 , _bib2doi_selected =

work page doi:10.1016/j.tcs.2008.06.046 2008
[22]

Proceedings of the forty-second ACM symposium on Theory of computing , pages =

An improved LP-based approximation for Steiner tree , author =. Proceedings of the forty-second ACM symposium on Theory of computing , pages =. 2010 , timestamp =. doi:10.1145/1806689.1806769 , _bib2doi_selected =

work page doi:10.1145/1806689.1806769 2010
[23]

1991 , publisher =

Dynamic Steiner tree problem , author =. 1991 , publisher =. doi:10.1137/0404033 , url =

work page doi:10.1137/0404033 1991
[24]

SIAM Journal on Computing , volume =

The power of recourse for online MST and TSP , author =. SIAM Journal on Computing , volume =. 2016 , publisher =. doi:10.1137/130917703 , _bib2doi_selected =

work page doi:10.1137/130917703 2016
[25]

On-line Generalized Steiner Problem , booktitle =

Baruch Awerbuch and Yossi Azar and Yair Bartal , editor =. On-line Generalized Steiner Problem , booktitle =. 1996 , url =

work page 1996
[26]

Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages =

Online steiner tree with deletions , author =. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages =. 2014 , organization =. doi:10.1137/1.9781611973402.34 , _bib2doi_selected =

work page doi:10.1137/1.9781611973402.34 2014
[27]

1995 , publisher =

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks , author =. 1995 , publisher =. doi:10.1137/S0097539792236237 , url =

work page doi:10.1137/s0097539792236237 1995
[28]

1995 , publisher =

A general approximation technique for constrained forest problems , author =. 1995 , publisher =. doi:10.1137/S0097539793242618 , url =

work page doi:10.1137/s0097539793242618 1995
[29]

Proceedings of the 2022

An Improved Analysis of Greedy for Online Steiner Forest , author =. Proceedings of the 2022. 2022 , organization =. doi:10.1137/1.9781611977073.125 , publisher =

work page doi:10.1137/1.9781611977073.125 2022
[30]

Breaking a Long-Standing Barrier: 2- Approximation for Steiner Forest , author =. 66th. 2025 , timestamp =. doi:10.1109/FOCS63196.2025.00023 , publisher =

work page doi:10.1109/focs63196.2025.00023 2025
[31]

SIAM Journal on Computing , volume =

Chen, Ho-Lin and Roughgarden, Tim and Valiant, Gregory , title =. SIAM Journal on Computing , volume =. 2010 , doi =

work page 2010
[32]

Westbrook and Dicky C

Jeffery R. Westbrook and Dicky C. K. Yan , title =. Mathematical Systems Theory , volume =. 1995 , publisher =. doi:10.1007/BF01185867 , timestamp =

work page doi:10.1007/bf01185867 1995
[33]

1997 , isbn =

Berman, Piotr and Coulston, Chris , title =. 1997 , isbn =. doi:10.1145/258533.258618 , booktitle =

work page doi:10.1145/258533.258618 1997
[34]

A Local-Search Algorithm for Steiner Forest , booktitle =

Martin Gro. A Local-Search Algorithm for Steiner Forest , booktitle =. 2018 , url =. doi:10.4230/LIPIcs.ITCS.2018.31 , timestamp =

work page doi:10.4230/lipics.itcs.2018.31 2018
[35]

32 Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi

Albert Gu and Anupam Gupta and Amit Kumar , editor =. The power of deferral: maintaining a constant-competitive steiner tree online , booktitle =. 2013 , url =. doi:10.1145/2488608.2488674 , timestamp =

work page doi:10.1145/2488608.2488674 2013
[36]

Kou and George Markowsky and Leonard Berman , title =

Lawrence T. Kou and George Markowsky and Leonard Berman , title =. Acta Informatica , volume =. 1981 , url =. doi:10.1007/BF00288961 , timestamp =

work page doi:10.1007/bf00288961 1981
[37]

On the Facility Location Problem in Online and Dynamic Models , booktitle =

Xiangyu Guo and Janardhan Kulkarni and Shi Li and Jiayi Xian , editor =. On the Facility Location Problem in Online and Dynamic Models , booktitle =. 2020 , url =. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.42 , timestamp =

work page doi:10.4230/lipics.approx/random.2020.42 2020
[38]

and Parotsidis, Nikos and Saulpic, David and Schwiegelshohn, Chris , title =

Cohen-Addad, Vincent and Hjuler, Niklas Oskar D. and Parotsidis, Nikos and Saulpic, David and Schwiegelshohn, Chris , title =. Advances in Neural Information Processing Systems (NeurIPS) , pages =. 2019 , timestamp =

work page 2019
[39]

and Kao, Ming-Yang and Krishnan, P

Grove, Edward F. and Kao, Ming-Yang and Krishnan, P. and Vitter, Jeffrey Scott , title =. Workshop on Algorithms and Data Structures , pages =. 1995 , timestamp =. doi:10.1007/3-540-60220-8_62 , _bib2doi_selected =

work page doi:10.1007/3-540-60220-8_62 1995
[40]

and Lin, Henry , title =

Chaudhuri, Kamalika and Daskalakis, Constantinos and Kleinberg, Robert D. and Lin, Henry , title =. IEEE INFOCOM 2009 , pages =. 2009 , timestamp =. doi:10.1109/INFCOM.2009.5062016 , _bib2doi_selected =

work page doi:10.1109/infcom.2009.5062016 2009
[41]

2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

Bosek, Bartlomiej and Leniowski, Dariusz and Sankowski, Piotr and Zych, Anna , title =. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2014 , timestamp =. doi:10.1109/FOCS.2014.48 , _bib2doi_selected =

work page doi:10.1109/focs.2014.48 2014
[42]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC) , pages =

Phillips, Steven and Westbrook, Jeffery , title =. Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC) , pages =. 1993 , timestamp =. doi:10.1145/167088.167201 , _bib2doi_selected =

work page doi:10.1145/167088.167201 1993
[43]

Journal of Algorithms , volume =

Westbrook, Jeffery , title =. Journal of Algorithms , volume =. 2000 , timestamp =. doi:10.1006/jagm.2000.1074 , _bib2doi_selected =

work page doi:10.1006/jagm.2000.1074 2000
[44]

and Zhang, Lisa , title =

Andrews, Matthew and Goemans, Michel X. and Zhang, Lisa , title =. Algorithmica , volume =. 1999 , timestamp =. doi:10.1007/PL00009263 , _bib2doi_selected =

work page doi:10.1007/pl00009263 1999
[45]

Online Scheduling with Bounded Migration , urldate =

Peter Sanders and Naveen Sivadasan and Martin Skutella , journal =. Online Scheduling with Bounded Migration , urldate =. 2009 , timestamp =. doi:10.1287/moor.1090.0381 , _bib2doi_selected =

work page doi:10.1287/moor.1090.0381 2009
[46]

A Robust

Martin Skutella and Jos. A Robust. Algorithms -. 2010 , url =. doi:10.1007/978-3-642-15775-2_4 , timestamp =

work page doi:10.1007/978-3-642-15775-2_4 2010
[47]

Algorithmica , volume =

Epstein, Leah and Levin, Asaf , title =. Algorithmica , volume =. 2014 , timestamp =. doi:10.1007/s00453-012-9718-3 , _bib2doi_selected =

work page doi:10.1007/s00453-012-9718-3 2014
[48]

Plotkin and Orli Waarts , title =

Baruch Awerbuch and Yossi Azar and Serge A. Plotkin and Orli Waarts , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.1999.1662 , timestamp =

work page doi:10.1006/jcss.1999.1662 2001
[49]

Maintaining Assignments Online: Matching, Scheduling, and Flows , booktitle =

Anupam Gupta and Amit Kumar and Cliff Stein , editor =. Maintaining Assignments Online: Matching, Scheduling, and Flows , booktitle =. 2014 , url =. doi:10.1137/1.9781611973402.35 , timestamp =

work page doi:10.1137/1.9781611973402.35 2014
[50]

Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse , booktitle =

Ravishankar Krishnaswamy and Shi Li and Varun Suriyanarayana , editor =. Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse , booktitle =. 2023 , url =. doi:10.1145/3564246.3585222 , timestamp =

work page doi:10.1145/3564246.3585222 2023
[51]

Dynamic set cover: improved algorithms and lower bounds , booktitle =

Amir Abboud and Raghavendra Addanki and Fabrizio Grandoni and Debmalya Panigrahi and Barna Saha , editor =. Dynamic set cover: improved algorithms and lower bounds , booktitle =. 2019 , url =. doi:10.1145/3313276.3316376 , timestamp =

work page doi:10.1145/3313276.3316376 2019
[52]

A New Deterministic Algorithm for Dynamic Set Cover , booktitle =

Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , editor =. A New Deterministic Algorithm for Dynamic Set Cover , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00033 , timestamp =

work page doi:10.1109/focs.2019.00033 2019
[53]

Monochromatic Triangles, Triangle Listing and

Anupam Gupta and Roie Levin , editor =. Fully-Dynamic Submodular Cover with Bounded Recourse , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00110 , timestamp =

work page doi:10.1109/focs46700.2020.00110 2020
[54]

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , booktitle =

Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai and Xiaowei Wu , editor =. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.150 , timestamp =

work page doi:10.1137/1.9781611976465.150 2021
[55]

Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach , booktitle =

Sepehr Assadi and Shay Solomon , editor =. Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ESA.2021.8 , timestamp =

work page doi:10.4230/lipics.esa.2021.8 2021
[56]

Efficient and Stable Fully Dynamic Facility Location , booktitle =

Sayan Bhattacharya and Silvio Lattanzi and Nikos Parotsidis , editor =. Efficient and Stable Fully Dynamic Facility Location , booktitle =. 2022 , url =

work page 2022
[57]

Dynamic Representations of Sparse Graphs , booktitle =

Brodal, Gerth St. Dynamic Representations of Sparse Graphs , booktitle =. 1999 , publisher =. doi:10.1007/3-540-48447-7_34 , _bib2doi_selected =

work page doi:10.1007/3-540-48447-7_34 1999
[58]

Near-optimal fully dynamic densest subgraph , booktitle =

Saurabh Sawlani and Junxing Wang , editor =. Near-optimal fully dynamic densest subgraph , booktitle =. 2020 , url =. doi:10.1145/3357713.3384327 , timestamp =

work page doi:10.1145/3357713.3384327 2020
[59]

Bera and Sayan Bhattacharya and Jayesh Choudhari and Prantar Ghosh , editor =

Suman K. Bera and Sayan Bhattacharya and Jayesh Choudhari and Prantar Ghosh , editor =. A New Dynamic Algorithm for Densest Subhypergraphs , booktitle =. 2022 , url =. doi:10.1145/3485447.3512158 , timestamp =

work page doi:10.1145/3485447.3512158 2022
[60]

2020 , issue_date =

Solomon, Shay and Wein, Nicole , title =. 2020 , issue_date =. doi:10.1145/3392724 , journal =

work page doi:10.1145/3392724 2020
[61]

5 Sepehr Assadi and Shay Solomon

Sepehr Assadi and Krzysztof Onak and Baruch Schieber and Shay Solomon , editor =. Fully dynamic maximal independent set with sublinear update time , booktitle =. 2018 , url =. doi:10.1145/3188745.3188922 , timestamp =

work page doi:10.1145/3188745.3188922 2018
[62]

2012 , issue_date =

Baswana, Surender and Khurana, Sumeet and Sarkar, Soumojit , title =. 2012 , issue_date =. doi:10.1145/2344422.2344425 , journal =

work page doi:10.1145/2344422.2344425 2012
[63]

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary , booktitle =

Sayan Bhattacharya and Thatchaphol Saranurak and Pattara Sukprasert , editor =. Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.ESA.2022.17 , timestamp =

work page doi:10.4230/lipics.esa.2022.17 2022
[64]

Online Maximum Matching with Recourse , booktitle =

Spyros Angelopoulos and Christoph D. Online Maximum Matching with Recourse , booktitle =. 2018 , url =. doi:10.4230/LIPIcs.MFCS.2018.8 , timestamp =

work page doi:10.4230/lipics.mfcs.2018.8 2018
[65]

Forty-second International Conference on Machine Learning,

Competitively Consistent Clustering , author =. Forty-second International Conference on Machine Learning,. 2025 , url =

work page 2025
[66]

The Thirteenth International Conference on Learning Representations , year =

Online Clustering with Nearly Optimal Consistency , author =. The Thirteenth International Conference on Learning Representations , year =

work page
[67]

A Generalized Matching Reconfiguration Problem , booktitle =

Noam Solomon and Shay Solomon , editor =. A Generalized Matching Reconfiguration Problem , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ITCS.2021.57 , timestamp =

work page doi:10.4230/lipics.itcs.2021.57 2021
[68]

Fully-Dynamic Load Balancing , booktitle =

Ayoub Foussoul and Vineet Goyal and Amit Kumar , editor =. Fully-Dynamic Load Balancing , booktitle =. 2024 , url =. doi:10.1007/978-3-031-59835-7_14 , timestamp =

work page doi:10.1007/978-3-031-59835-7_14 2024
[69]

URL:https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.ITCS.2017.51,doi:10.4230/LIPIcs.ITCS.2017.51

Bernstein, Aaron and Kopelowitz, Tsvi and Pettie, Seth and Porat, Ely and Stein, Clifford , title =. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.ITCS.2017.51 , annote =

work page doi:10.4230/lipics.itcs.2017.51 2017
[70]

Karlin and Sherry Sarkar , editor =

Niv Buchbinder and Anupam Gupta and Daniel Hathcock and Anna R. Karlin and Sherry Sarkar , editor =. Maintaining Matroid Intersections Online , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.149 , timestamp =

work page doi:10.1137/1.9781611977912.149 2024
[71]

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =

Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Cliff Stein and Madhu Sudan , editor =. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00032 , timestamp =

work page doi:10.1109/focs.2019.00032 2019
[72]

11 Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time , author =. CoRR , volume =. 2025 , eprint =. doi:10.48550/arXiv.2511.08485 , timestamp =

work page doi:10.48550/arxiv.2511.08485 2025
[73]

CoRR , volume =

Shay Solomon and Amitai Uzrad , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2511.07354 , eprinttype =. 2511.07354 , timestamp =

work page doi:10.48550/arxiv.2511.07354 2025
[74]

Shay Solomon and Amitai Uzrad and Tianyi Zhang , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00025 , timestamp =

work page doi:10.1109/focs61266.2024.00025 2024
[75]

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-

Anton Bukov and Shay Solomon and Tianyi Zhang , editor =. Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-. Proceedings of the 2025 Annual. 2025 , url =. doi:10.1137/1.9781611978322.24 , timestamp =

work page doi:10.1137/1.9781611978322.24 2025
[76]

Optimal Dynamic Distributed

Keren Censor. Optimal Dynamic Distributed. Proceedings of the 2016. 2016 , url =. doi:10.1145/2933057.2933083 , timestamp =

work page doi:10.1145/2933057.2933083 2016
[77]

A Borsuk-Ulam lower bound for sign-rank and its applications

Shay Solomon and Amitai Uzrad , editor =. Dynamic ((1+. Proceedings of the 55th Annual. 2023 , url =. doi:10.1145/3564246.3585211 , timestamp =

work page doi:10.1145/3564246.3585211 2023
[78]

CoRR , volume =

Niv Buchbinder and Joseph Naor and David Wajc , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2511.13605 , eprinttype =. 2511.13605 , timestamp =

work page doi:10.48550/arxiv.2511.13605 2025
[79]

Consistent Submodular Maximization , booktitle =

Paul Duetting and Federico Fusco and Silvio Lattanzi and Ashkan Norouzi. Consistent Submodular Maximization , booktitle =. 2024 , url =

work page 2024
[80]

The Cost of Consistency: Submodular Maximization with Constant Recourse , booktitle =

Paul D. The Cost of Consistency: Submodular Maximization with Constant Recourse , booktitle =. 2025 , url =. doi:10.1145/3717823.3718131 , timestamp =

work page doi:10.1145/3717823.3718131 2025

Showing first 80 references.