How to match when all vertices arrive online

DOI10.1145/3188745.3188858zbMath1428.68394arXiv1802.03905OpenAlexW2963014036MaRDI QIDQ5230273

Yu-Hao Zhang, Xue Zhu, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Zhi-Yi Huang

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

randomized primal-dualfully online matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (7)

Online total bipartite matching problem ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ Computing maximum matchings in temporal graphs ⋮ Best fit bin packing with random order revisited ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ Stochastic Online Metric Matching

This page was built for publication: How to match when all vertices arrive online