Events
Fall 2022

Data-Driven Decision Processes Seminar

Tuesday, November 22nd, 2022, 1:00 pm2:00 pm

Add to Calendar

Speaker: 

Will Ma (Columbia)

Location: 

Room 116

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.