Fully online matching

DOI10.1145/3390890MaRDI QIDQ5133972zbMATH OpenOpenAlexWikidataFDO

Authors Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yu-Hao Zhang, Xue Zhu, Zhiyi Huang

Publication date 11 November 2020

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

Full work available at URL https://doi.org/10.1145/3390890

zbMATH Keywords

online matchingranking

Mathematics Subject Classification ID

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

Recommendations

• How to match when all vertices arrive online
• Tight competitive ratios of classic matching algorithms in the fully online model
• Tighter bounds for online bipartite matching
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs

Cited in

(15)

• Deferred on-line bipartite matching
• A stronger impossibility for fully online matching
• Tighter bounds for online bipartite matching
• Prophet matching with general arrivals
• Technical note -- Online hypergraph matching with delays
• How to match when all vertices arrive online
• Tight competitive ratios of classic matching algorithms in the fully online model
• Adwords in a panorama
• Online matching on 3-uniform hypergraphs
• Comparing the hardness of online minimization and maximization problems with predictions
• Almost tight bounds for online hypergraph matching
• Class fairness in online matching
• Toward a better understanding of randomized greedy matching
• Random order vertex arrival contention resolution schemes for matching, with applications
• The greedy algorithm is not optimal for on-line edge coloring

This page was built for publication: Fully online matching

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