Rounding dynamic matchings against an adaptive adversary

DOI10.1145/3357713.3384258MaRDI QIDQ5144908zbMATH OpenOpenAlexFDO

Authors David Wajc

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.05545

zbMATH Keywords

adaptive adversarydynamic algorithmsdynamic matchingmatching sparsifier

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(10)

• Deterministic dynamic matching in worst-case update time
• On regularity lemma and barriers in streaming and dynamic matching
• Decremental matching in general weighted graphs
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• A generalized matching reconfiguration problem
• Deterministic rounding of dynamic fractional matchings
• The greedy algorithm is not optimal for on-line edge coloring
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Minimizing recourse in an adaptive balls and bins game

This page was built for publication: Rounding dynamic matchings against an adaptive adversary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144908)