Technical Report PHD-2008-11

Title: Designing Competitive Online Algorithms via a Primal-Dual Approach
Authors: Niv Buchbinder
Supervisors: Seffi Naor
Abstract: 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2008
To the main CS technical reports page

Computer science department, Technion