Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

New Models and Improved Bounds for Online Optimization
event speaker icon
David Naori (Ph.D. Thesis Seminar)
event date icon
Sunday, 15.01.2023, 15:00
event location icon
Zoom Lecture: 91014628593 and Taub 401
event speaker icon
Advisor: Prof. Danny Raz
We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the secretary problem and online matching problems in our new models. We also study the online facility location problem and obtain improved bounds in the standard random-order model.