Abstract 

Online Contention Resolution Schemes (OCRS's) are a useful tool for performing sequential randomized rounding when each arriving element is only eligible to be selected with a known, independent probability. They have led to some best-known guarantees in prophet inequalities, stochastic probing, and online matching problems, among others.  We focus on the feasibility structure where the elements correspond to edges in a graph and the selected subset must form a matching.  We discuss state-of-the-art results in various settings, contrasting edge arrival vs. vertex arrival, general vs. bipartite graphs, vanishing vs. general probabilities, and different arrival orders. The tight guarantee in most settings remains unknown, compared to other feasibility structures (e.g. matroids, knapsacks), and we discuss some of the challenges faced.

Based on joint works with Calum MacRury (Columbia), Nathaniel Grammel (Maryland), and Pranav Nuti (Stanford).

Time

2024-06-03  15:30 - 16:30   

Speaker

Will Ma, Columbia Business School

Room

Room 308