The Taub Faculty of Computer Science Events and Talks

In this work we study a wide range of online covering and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design and analysis of online algorithms for this large class of problems. In particular, our analysis uses weak duality rather than a tailor made (i.e., problem specific) potential function. We show how to apply the primal-dual approach to many interesting problems. Examples consist of the ski rental problem, dynamic TCP acknowledgement, routing, load balancing, online versions of set-cover, graph connectivity problems and even the problem of allocating ad-auctions. Recently, we used the primal-dual approach to design an optimal randomized $O(\log k)$-competitive algorithm for the weighted caching problem, where $k$ is the cache size. This is the first randomized $o(k)$-algorithm for this problem which has been open for the last 18 years. We also discuss extensions of this work to several models of generalized caching.