Primal-dual Algorithms for Online Optimization Seffi Naor Technion 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 on the constrained Steiner forest network design problem. In this series of lectures we show how to extend the primal-dual method to the setting of online algorithms. In an online problem the input is revealed in parts and the main issue is obtaining good performance in the face of uncertainty. A standard measure for evaluating the performance of an online algorithm is the competitive ratio, which compares the performance of an online algorithm to that of an offline algorithm which is given the whole input sequence beforehand. We show how to apply the primal-dual approach to a wide variety of interesting online problems. This approach has allowed us to view previously suggested algorithms in a unified way, as well as obtain improved competitive factors for classic problems. 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 competitive ratio analysis 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 and hence stronger. Lecture 1: Topics: Introduction to competitive analysis, ski problem, paging (LRU), randomized competitive analysis, marking algorithm, linear programming, duality, set cover, dual fitting analysis of greedy. Online primal-dual framework: Examples: ski problem, online set cover, online routing. Lecture 2: Topics: General framework: covering and packing. Online graph optimization problems Routing and load balancing. Lecture 3: Topics: Maximizing revenue from adauctions Weighted paging.