המחלקה למדעי המחשב - אוניברסיטת בר-אילן

Department of Computer Science - Bar-Ilan University

קולוקוויום במדעי המחשב

Computer Science Colloquium

Danny Raz

Technion

Will lecture on

Towards Better Practical Online Algorithms Based on Theoretical Insight

Online algorithms have proven to be an important tool in studying interactive scenarios where the input is revealed over time and one has to take decisions before seeing all the input.  The analysis in the worst-case adversarial model provides robust guarantees of the expected performance when the algorithm has no prior knowledge about the input.  However, in some cases, this model is too powerful and no algorithm can achieve a non-trivial competitive-ratio (e.g., the secretary problem). In other cases, different algorithms provide similar worst-case guarantee, and thus the model does not help to select the best algorithm for the problem at hand.  Moreover, in many online scenarios, we have additional information about the input (e.g., data from past requests) and this knowledge is not represented in the model. Thus, current theoretical works produce novel interesting algorithms that have limited practical impact, while works that address realistic problems lack a robust theoretical foundation and do not provide performance guarantees. 

In this talk, I will address this gap by describing a new theoretical online model that extends the standard online worst-case model to accommodate prior knowledge. This is done 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. We analyze the classical secretary problem under two variants of this new model, and then present an algorithm for the practical problem of placing virtual machines in data centers. We analyze this new competitive online algorithm for multidimensional resource allocation in and present  guaranteed performance. Moreover, using extensive simulation over real data from Google and AWS, we also demonstrate that this new approach yields much higher revenue to cloud providers than currently used heuristics.

This is a joint work with David Naori and Haim Kaplan.