Title:

Online Contention Resolution Schemes for the Matching Polytope of Graphs''

Abstract:

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. This includes the prophet matching problem for both edge and vertex arrival models, as well as for matching in a gig-economy. Our techniques are also relevant to more complicated resource constraints, and we attain new results for network revenue management and online assortment optimization. 

Bio:

Calum MacRury is a Postdoctoral Research Scholar in the Decision, Risk, and Operations Division at Columbia Business School, where he is supported by
an NSERC Postdoctoral Fellowship (PDF). 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.