 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
| [Home page] | [The MPRI course] | [Administrative organisation] | [Practical information] |
Person in charge: Frédéric Magniez
| F. Magniez | CR | CNRS | LRI |
| A. Rosen | DR | CNRS | LRI |
| M. de Rougemont | PU | Paris 2 | LRI |
| M. Santha | DR | CNRS | LRI |
Streaming algorithms and online algorithms are two types of algorithms which are restricted in the way they can access and process their input. Online algorithms receive their input piece by piece, and have to take an irrevesible action upon receipt of each piece. Streaming algorithms read their input piece by piece, are further restricted in the amount of memory at their disposal, and have to compute a function (or an approximation of a fuction) of the whole input. This course is aimed at giving an introduction to these two types of algorithms and to their analysis.
The area of streaming algorithms has experienced a tremendous growth over the last decade; computing over continuous streams of data using only a limited amount of memory has become of key importance in many applications. The design of streaming algorithms is motivated by the recent considerable growth of the size of the data that algorithms are called upon to process in everyday real-time applications, for example in bioinformatics for genome decoding, in Web databases for the search of documents, or in network monitoring.
In this context, inputs are too large to be loaded in memory in their entirety due to the limitation on the amoung of memory. Moreover, there is an additional restriction of one-time sequential scan of the input (and not e.g., random access to the input).
The goal of this course is to provide an introduction to some of the key issues in streaming algorithm, with the emphasis on theoretical tools for designing and analyzing efficient data stream algorithms.
The area of online algorithms has become an established field in theoretical computer science. It deals with the design and analysis of algorithms that operate in a state of incomplete information. Typically, an online algorithm receives its input piece by piece, and must take an irreversible action upon the receipt of each piece of input without knowledge of future input. Such scenarios are predominant and occur, e.g., in the management of (limited space) cache, in admission and routing in communication networks, in scheduling, etc.
When no prediction of the pattern of the input sequence is available, an accepted method to analyze the performance of online algorithms is "competitive analysis". In competitive analysis one compares the performance (e.g., overall system cost) of an online algorithm, to the performance of an utopian, clairvoyant, algorithm, that knows the entire input in advance. This type of analysis allows one to obtain robust results that do not depend on specific input patterns.
In this course we will try to present the basic concepts of online algorithms and competitive analysis, to cover a number of "classical" results (e.g., k-server problems, metrical task systems), as well as some recent research directions and open problems.
The topics discussed will come from the following list (subject to some changes; probably not all topics will be covered).
General knowledge in algorithms and complexity theory.
Internships and PhD proposals of research team Algorithms and Complexity of LRI