Competitive Online Algorithms

Course Contents

Online algorithms represent a relatively new area of research that has developed in the past ten years. An online algorithm receives the input incrementally, one piece at a time, and must process each input portion without knowing future portions. An online algorithm A is called c-competitive if, for every input sequence, the cost incurred by A is at most c times the optimal offline cost for that sequence. In this mini-course we will present the most important concepts and techniques used in the study of deterministic and randomized online algorithms.

Research on online algorithms in generally motivated by real online problems that arise in practice. In the mini-course we will discuss in detail algorithms for the following applications.