|
3:30 PM - 4:30 PM, LH 5 Optimal Stopping: Prophets and Secretaries Ashish Chiplunkar EPFL Lausanne. 28-02-19 Abstract The prophet and the secretary problems are fundamental problems in optimal stopping theory, and concern choosing one out of an online sequence of numbers, with the objective of maximizing the (expectation of) the number picked. In the prophet problem, the numbers are drawn independently from a given sequence of probability distributions, whereas in the secretary problem, the numbers are chosen adversarially but arrive in a random order. These problems have been studied extensively, and tight bounds on the performance of algorithms are known. In the prophet secretary problem independent samples from a known set of distributions arrive in a random order, and this problem remains poorly understood. In this talk, I will present some fundamental algorithmic and hardness results related to the prophet and the prophet secretary problems, and a survey of results on other closely related problems.
|
