An Experimental Study of Algorithms for Online Bipartite Matching

DOI10.1145/3379552zbMath1521.68091arXiv1808.04863OpenAlexW3011788258MaRDI QIDQ6039931

Christodoulos Karavasilis, Allan Borodin, Denis Pankratov

Publication date: 23 May 2023

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphsbipartite matchinggreedy algorithmsstochastic input models

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Learn from history for online bipartite matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On extensions of the deterministic online model for bipartite matching and max-sat
• Bayesian Mechanism Design
• Are Stable Instances Easy?
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Dependent rounding and its applications to approximation algorithms
• Improved Bounds for Online Stochastic Matching
• Random graph models of social networks
• A critical point for random graphs with a given degree sequence
• Greedy Bipartite Matching in Random Type Poisson Arrival Model
• Online Stochastic Matching: Beating 1-1/e
• Online Stochastic Matching: New Algorithms with Better Bounds
• Heuristic initialization for bipartite matching problems
• Online bipartite matching with random arrivals
• Power balance and apportionment algorithms for the United States Congress
• Power balance and apportionment algorithms for the United States Congress
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
• On conceptually simple algorithms for variants of online bipartite matching

This page was built for publication: An Experimental Study of Algorithms for Online Bipartite Matching