Data-Driven Decision Processes - Whiteboard Talk

Title: Combinatorial Optimization in the Prophet and Random Order Models
Speaker: Anupam Gupta (Carnegie Mellon University)

Abstract: In her boot-camp talk Shuchi Chawla introduced the secretary (i.e., random order) and prophet (i.e., independent draws from given distributions) models as two ways to mitigate the strong requirements of the online competitive analysis model. Her talk focused on the problem of picking 1 or k items (though she alluded to many more applications). Later Thomas and Alex (in a whiteboard lecture) talked about using balanced prices for prophet models. 

My talk will be about a broader set of problems with more combinatorial structure (e.g., spanning trees, set cover, min-cost matchings, packing LPs) and indicate how assumptions about the arrival order can give better/refined guarantees.