Online Contention Resolution Schemes (OCRS's) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS's have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions---accept/reject, probing, pricing---in a unified manner. We analyze OCRS's for resource constraints defined by graph matchings, a fundamental structure in combinatorial optimization. We improve the state of the art both in terms of algorithmic guarantees and impossibility results. Our algorithms directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs. Most notably, this includes the prophet matching problem for both edge and vertex arrival models.
Calum MacRury is a Postdoctoral Research Scholar in the Decision, Risk, and Operations Division at Columbia Business School, where he works on online algorithms, and more generally, decision making under uncertainty. He is particularly interested in stochastic optimization, including prophet inequalities and probing problems when the resource constraints are described by graph matchings. Calum received his PhD from the Department of Computer Science at the University of Toronto in 2023.