Ph.D Thesis

Ph.D StudentBuchbinder Niv
SubjectDesigning Competitive Online Algorithms
via a Primal-Dual Approach
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


The primal-dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms. The method has its origins in the realm of exact algorithms, e.g., for matching and network flow. In the area of approximation algorithms the primal-dual method has emerged as an important unifying design methodology starting from the seminal work of Goemans and Williamson.

We show in this thesis how to extend the primal-dual method to the setting of online algorithms, and show its  applicability to a wide variety of interesting problems. Among the online problems that we consider here are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing and the problem of allocating ad-auctions. We also show that classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be optimally solved using a simple primal-dual approach.

The primal-dual method has several advantages over existing methods. First, it gives a general recipe for the design and analysis of online algorithms. The analysis of the competitive ratio is direct, without a potential function appearing ``out of nowhere". Finally, since the analysis is done via duality, the competitiveness of the online algorithm is with respect to an optimal fractional solution which can be advantageous in certain scenarios.