The course will be given in English.
The exam will be available both in French and in English, and can be written by the students in either language.
Lecture notes
There are no lecture notes. The lectures will be given on the board.
Some optional exercises and additional reading will be suggested during the course.
Goals
Approximation algorithms and online algorithms are two algorithmic paradigms which deal with two kinds of difficulties that arise in computing exact solutions that arise in computation.
On the one hand, today, most applied optimization problems suffer from the fact that finding exact solutions to them is NP-hard and if one wants to be computationally feasible, one has to settle for finding approximate solutions to these problems. This is the content of approximation algorithms: to understand the approximability of NP-hard problems.
On the other hand, several computationally "easy" problems become hard when the input is revealed piece by piece, and the algorithms have to take an irrevesible action upon receipt of each piece. This is often the case in several "data intensive" problems that arise in practice. Here again, one has to settle for computing approximate solutions, and the study of problems in this model constitutes the area of online algorithms.
This course is aimed at giving an introduction to these two types of algorithmic paradigms and to their analysis.
Approximation algorithms
Approximation algorithms has been, perhaps, the most intensively studied area for more than 2 decades. The main content of this area is to cope with NP-hardness. NP-hardness is ubiquitous: almost any computational problem that arises in practice or otherwise today is likely to be NP-hard to solve exactly. This forces us to consider the search for "approximate" solutions in time polynomial in the size of the inputs. On the other hand, several problems remain hard even when is required to compute approximate solutions. This is more recent and has revolutionized our understanding of the whole area itself.
Morevoer, the research today in this area brings together rich and deep mathematical fields. This course will consist of samples from current research frontiers in the theory of approximability of NP-hard problems. It will be geared towards providing its student, not only the breadth and the applicability of this area but also, a wide range of mathematical techniques prevalent and driving it.
Online 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.
Course program
The topics discussed will come from the following list (subject to some changes; probably not all topics will be covered).
Approximation algorithms
Motivation and Introduction
Combinatorial Algorithms: Vertex Cover, Set Cover, Metric/Euclidean TSP
Linear Programming based Algorithms: Sparsest Cut, Steiner Network, Facility Location, k-Median
Semidefinite Programming based Algorithms: Max Cut, Sparsest Cut
Hardness of Approximation
Online algorithms
Motivation and introduction
Paging (cache replacement)
The k-server problem
Search problems: "the cow problem"; Navigation in unknown terrain
Metrical task systems
The power of randomness: relative power of adversaries versus randomized online algorithms
Online load balancing algorithms
Online algorithms in communication networks
Prerequisites
General knowledge in algorithms and complexity theory.
![[arobase]](./commercial_at.png){kind=small}
mpri![[point]](./full_stop.png){kind=small}
master![[Version Française]](./french_flag.png)