In this paper we study a data-driven variant of the classical problem: The cardinality of the sequence is unknown and both the values and the order are adversarial, but we are given a set of samples in advance. These samples are drawn from the adversarial input and they represent historical data available to us. The remaining part of the input arrives online, and we want to pick the maximum element. We present a single-threshold algorithm which accepts the first value that is above the k’th largest sample, for a suitable chosen k. Although very simple, we show that this algorithm is optimal. To do so, we introduce a new technique, which is based on interpreting the model as a game on a graph. This approach might be of independent interest.
Next, we explore the “prophet variant” for this model. The performance measure now is the worst-case ratio between the expected value that the algorithm gets and the expected optimal value of the online set. Again, we examine the performance that simple, deterministic algorithms achieve.
This is ongoing work with José Correa, Laurent Feuilloley and Tim Oosterwijk.
Date: Monday 11th of May 2020, starting at 2 p.m.
The seminar will take place online. If you are a TUM-member and want to join, though you have not received the link via e-mail, please contact adone(at)tum.de