Online Bipartite Matching with Amortized O (log 2 n ) Replacements

DOI10.1145/3344999zbMath1473.68217arXiv1707.06063OpenAlexW2974337481MaRDI QIDQ5215466

Eva Rotenberg, Aaron Bernstein, Jacob Holm

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmsbipartite graphsmaximum matchingload balancingshortest augmenting path

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (4)

Online load balancing with general reassignment cost ⋮ The power of amortized recourse for online graph problems ⋮ Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem ⋮ Unnamed Item

This page was built for publication: Online Bipartite Matching with Amortized O (log ² n ) Replacements