Seminar: Online Contention Resolution Schemes for Stochastic Matching Problems
- Date
- November 28, 2023
- Time
- 12:00 PM EST - 1:00 PM EST
- Location
- ENG-210 and virtually via zoom
- Open To
- All faculty, staff, students and guests are welcome to attend
- Contact
- Pawel Pralat (pralat@torontomu.ca)
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.