Maximum Matching in the Online Batch-arrival Model

DOI10.1145/3399676OpenAlexW3044919769MaRDI QIDQ5888940FDOQ5888940

Authors: Euiwoong Lee, Sahil Singla 

Publication date: 26 April 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

Recommendations

• Maximum matching in the online batch-arrival model
• Online algorithms for maximum cardinality matching with edge arrivals
• Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
• Online algorithms for maximum cardinality matching with edge arrivals
• Deferred on-line bipartite matching

zbMATH Keywords

matchingcompetitive ratioprimal-dual analysisEdmonds-Gallai decompositionsemi-streamingOnlineAlgorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (2)

• Risk‐averse optimization and resilient network flows
• Online 2-stage stable matching

This page was built for publication: Maximum Matching in the Online Batch-arrival Model

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