4 citations · 28 across the 18 of their papers we have counts for
4 papers · 1 filter
Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
Brian Brubach, Nathaniel Grammel, Will Ma +2
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the…
Perfect Matchings in the Semi-random Graph Process
Pu Gao, Calum MacRury, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
The Phase Transition of Discrepancy in Random Hypergraphs
Calum MacRury, Tomáš Masařík, Leilani Pai +1
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on vertices and edges. In the first (edge-independent)…
Prophet Matching Meets Probing with Commitment
Allan Borodin, Calum MacRury, Akash Rakheja
We consider the online stochastic matching problem for bipartite graphs where edges adjacent to an online node must be probed to determine if they exist, based on known edge probab…