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

competitive ratioEdmonds-Gallai decompositionmatchingOnlineAlgorithmsprimal-dual analysissemi-streaming

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

(4)

• Online 2-stage stable matching
• Risk‐averse optimization and resilient network flows
• Online algorithm for fractional matchings with edge arrivals in graphs of maximum degree three
• One-way communication complexity of minimum vertex cover in general graphs

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)