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

Designing Competitive Online Algorithms via a Primal-Dual Approach
event speaker icon
Niv Buchbinder (Ph.D. Thesis Seminar)
event date icon
Wednesday, 16.04.2008, 16:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. Seffi Naor
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.