competitive analysis 1graph algorithms 1online algorithms 1preemptive matching 1randomized algorithms 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DS2026
Online Preemptive Matching Revisited
Peter Kiss, Mohammad Sharifi
The paper establishes a new upper bound of 0.5661 on the competitive ratio for online preemptive matching, improving on the previous best bound and showing hardness even when optim…
cs.DS2025
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
cs.DS2025
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…