Markovian online matching algorithms on large bipartite random graphs

DOI10.1007/s11009-022-09973-yOpenAlexW3161488392MaRDI QIDQ2684964

Yanyan Li

Publication date: 17 February 2023

Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.04440

zbMATH Keywords

stochastic processesmatchingrandom graphsonline algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large graph limit for an SIR process in random network with heterogeneous connectivity
• Law of large numbers limits for many-server queues
• The fluid limit of a heavily loaded processor sharing queue
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• The jamming constant of uniform random graphs
• A functional central limit theorem for the \(M/GI/\infty \) queue
• Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
• Bigraphs versus digraphs via matrices
• Networks
• The Greedy Independent Set in a Random Graph with Given Degrees
• Approximate Maximum Matching in Random Streams
• Directed random graphs with given degree distributions
• Online Stochastic Matching: Beating 1-1/e
• Paths, Trees, and Flowers
• Online bipartite matching with random arrivals

This page was built for publication: Markovian online matching algorithms on large bipartite random graphs