Beating two-thirds for random-order streaming matching

DOI10.4230/LIPICS.ICALP.2021.19MaRDI QIDQ7241115zbMATH OpenFDO

Authors Sepehr Assadi, Soheil Behnezhad

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.19

zbMATH Keywords

maximum matchingrandom-order streamingstreaming

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A simple augmentation method for matchings with applications to streaming algorithms
• Approximate Maximum Matching in Random Streams
• Better bounds for matchings in the streaming model
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Faster fully dynamic matchings with small approximation ratios
• Fully dynamic matching in bipartite graphs
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Improved bounds for matching in random-order streams
• Maximum matching in semi-streaming with few passes
• On graph problems in a semi-streaming model
• On representatives of subsets.
• The Factorization of Linear Graphs
• Towards a unified theory of sparsification for matching problems
• Weighted Matchings via Unweighted Augmentations

Cited in

(1)

• Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries

This page was built for publication: Beating two-thirds for random-order streaming matching

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