Campus Event Calendar
Event Entry
What and Who
Combinatorial Optimization under Uncertainty and Prophet Inequalities
Vasilis Livanos
University of Illinois Urbana Champaign
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 23 November 2022
13:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
A classic result from optimal stopping theory asks when one should stop and accept a value presented one by one, if one knows the distributions that these values are coming from and wants to select the maximum. The catch is that, if one rejects a value, it can never be selected again. This setting, which combines online decision making with stochastic uncertainty, is called the prophet inequality. Over the past decade, there have been two very exciting discoveries, connecting auction theory and online combinatorial optimization with prophet inequality-type problems.
In this talk, we cover some of the standard ideas and results on prophet inequalities and online combinatorial optimization. We give some intuition about the connections mentioned before and show how one can develop tools
for online combinatorial optimization via a duality approach. Finally, we study a new direction that studies prophet inequalities for minimization instead, which present rich and qualitatively different results from the
maximization case.
Contact
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk online but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 11/10/2022 11:16
Roohani Sharma, 11/04/2022 11:36
Roohani Sharma, 10/27/2022 13:32 -- Created document.
Roohani Sharma, 11/04/2022 11:36
Roohani Sharma, 10/27/2022 13:32 -- Created document.