Greedy Matching in Bipartite Random Graphs

DOI10.1287/stsy.2021.0082zbMath1492.68099OpenAlexW3208317688MaRDI QIDQ5084502

Nick Arnosti

Publication date: 24 June 2022

Published in: Stochastic Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/stsy.2021.0082

zbMATH Keywords

matchingrandom graphsgreedy algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Cites Work

• Greedy matching: guarantees and limitations
• The average performance of the greedy matching algorithm
• (Incremental) priority algorithms
• Differential equations for random processes and random graphs
• Bayesian Mechanism Design
• Sharp load thresholds for cuckoo hashing
• AdWords and generalized online matching
• Tight Thresholds for Cuckoo Hashing via XORSAT
• Randomized greedy matching
• Randomized greedy matching. II
• Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• Towards a better understanding of randomized greedy matching
• Online Stochastic Matching: Beating 1-1/e
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• An Analysis of Random-Walk Cuckoo Hashing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Greedy Matching in Bipartite Random Graphs