This course is no longer offered

22927 Seminar: Online Algorithms

Credits: 3 graduate seminar graduate credits in Computer Science

Prerequisites: 12 credits in graduate courses in Computer Science with a GPA of at least 80

Required: Algorithms

The course is based on a reader edited by Leah Epstein.

The seminar deals with online algorithms and their theoretical analysis. An online algorithm does not get all its input in advance, but rather as it runs, and must make decisions under conditions of uncertainty. Analysis of this type of algorithms is called 'competitive analysis' and is compared to an optimal offline algorithm for which all input is known in advance. The measure for the quality of an online algorithm is the competitive ratio.

Many problems we encounter in real life are online problems and almost every decision we make in life is an online decision. For example, in buying an apartment we do not know what the foreign exchange rates will be at a given time in the future, and in hiring an employee we do not know whether a better candidate will come along in the future. There are many and varied examples.

Topics: The seminar deals with classic problems that are important in an online environment; for example, problems related to operating systems, in which needs change from one minute to the next and demands present themselves at different times, and problems with optical networks. Examples of such problems include balancing loads (between different processors on the same computer or between different paths in communication networks), scheduling (tasks), paging (replacing pages in the fast memory).

Structure: Each student specializes in a specific topic through close reading of a paper that presents an online problem and an algorithm for its solution. Most papers provide the lower bound of the algorithm competitiveness for the given problem. Acquaintance with several online problems will enable students to develop the thought processes required for dealing with online algorithms.