Maximum Matching in the Online Batch-arrival Model

DOI10.1145/3399676MaRDI QIDQ5888940zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

matchingcompetitive ratioprimal-dual analysisEdmonds-Gallai decompositionsemi-streamingOnlineAlgorithms

Mathematics Subject Classification ID

Computer science (68-XX)

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

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)