Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
From MaRDI portal
Publication:5236370
DOI10.1137/1.9781611975482.178zbMath1432.68590arXiv1810.07903OpenAlexW2897002186MaRDI QIDQ5236370
Runzhou Tao, Zhihao Gavin Tang, Binghui Peng, Xiaowei Wu, Yu-Hao Zhang, Zhi-Yi Huang
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.07903
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68) Online algorithms; streaming algorithms (68W27)
Related Items (8)
Online total bipartite matching problem ⋮ Prophet Matching with General Arrivals ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ Computing maximum matchings in temporal graphs ⋮ Best fit bin packing with random order revisited ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ A stronger impossibility for fully online matching ⋮ Stochastic Online Metric Matching
This page was built for publication: Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
