An Experimental Study of Algorithms for Online Bipartite Matching
From MaRDI portal
Publication:6039931
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
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