Data-Driven Decision Processes Seminar

Title: Prophets and Online Contention Resolution for k item copies, Knapsack, and Matching

Abstract: Online Contention Resolution Schemes (OCRS) is a useful tool for deriving prophet inequalities and general online resource allocation algorithms when arrivals come from known, independent distributions.  Complementing earlier talks on rank-1 matroids and general matroids, we focus on OCRS and Random-order OCRS for k-uniform matroids, the knapsack polytope, and the matching polytope.  We will discuss high-level differences between the techniques that have been useful in these different settings, and end with some open problems.

Describes results from joint work with Jiashuo Jiang & Jiawei Zhang (SODA '22), Nick Arnosti (EC '22), and Calum MacRury & Nathaniel Grammel (SODA '23). Jiashuo and Calum were also Simons visitors this term.