This year, the course will be held in the Thursday noon slot, in the second half of the first semester, i.e., starting at 12:45 on December 9, 2021.

We offer internships on the topic of this course.

Carola Doerr (chercheur CNRS, LIP6, Sorbonne Université)

• Carola Doerr: First half of the course
• Evripidis Bampis: Second half of the course

In previous years (from 2015 until 2020), the second half of the course was taught by

• Christoph Dürr.

This course will be held in English. Exam answers and project reports can be answered in English or French.

The current MPRI offer contains courses on different algorithmic problems, for which solutions are designed that are tailored to the problem at hand. These solutions are often exact, and their optimization times ideally (close to being) best possible. In this course we want to give a complementary view on algorithmics in computer science. We present general purpose heuristics which are widely applied to solve real-world optimization challenges, such as local search algorithms and randomizes search heuristics like Simulated Annealing and evolutionary algorithms. Our course focuses on the theoretical aspects of this area. Runtime bounds, complexity statements, and approximation ratios are rigorously proven in the course.

Some background on algorithms and probability theory (e.g., expected value, binomial distribution).

The course starts with a summary of solution techniques and problems that the students might have seen in their studies, for example local search algorithms for facility location. Then we introduce formally a few different popular heuristic approaches, such as random sampling, local search, simulated annealing, genetic algorithms. Theoretical background from both deterministic and randomized algorithm analysis will be introduced. Students will see how to apply them to show lower bounds and upper bounds on the performance of the different heuristics. Finally, we given an illustrative example, highlighting how to use insights from this course to design new efficient problem solvers.

For the first part of the lecture, a slide deck and relevant papers will be communicated by e-mail after each lecture. For the second part of the lecture, relevant papers will be either listed here or send around by e-mail.

The lecture itself will be mostly on the black board, the slide decks are not guaranteed to cover all content discussed in the course.

In-class exercises will help students (and the teachers ;)) identify topics that may require more discussion.

For the first part of the lecture, you can find some references here:

• Drift Analysis: survey and examples. https://arxiv.org/abs/1712.00964
• Black-Box Complexity: survey of models and results. https://arxiv.org/abs/1801.02037
• Online Parameter Selection: survey of known theoretical results: https://arxiv.org/abs/1804.05650
• Useful probabilistic tools: https://arxiv.org/abs/1801.06733

For the second part of the lecture, the following book is the main reference: Jon Kleinberg, Eva Tardos, Algorithm Design, Addison Wesley.

9.12.2021 [Carola] Introduction to heuristic search, motivation, applications. The Mastermind game, upper and lower bounds.

16.12.2021 (no lecture, sick leave)

6.1.2022 [Carola] Analysis of iterative optimization heuristics: general lower and upper bounds for the (1+1) Evolutionary Algorithm.

13.1.2022 (no lecture, sick leave)

20.1.2022 [Carola] Drift analysis, potential functions, the linear functions problem.

27.1.2022 [Evripidis] Local Search for Max-Cut, Hopfield Neural Networks and Local Search, Best response dynamics and Nash Equilibria for multicast under the fair share assumption

3.2.2022 [Evripidis] Modified Local Search for Max-Cut, Image Segmentation problem, Classification via Local Search

10.2.2022 [Evripidis] Classification via Local Search (continued), scheduling and local search, non-oblivious local search (max-k-sat)

17.2.2022 [Carola + Evripidis] Presentation of the reading assignments

24.2.2020 (no lecture)

10.3.2020 exam

There will be one extended homework and a final written exam. Final grading will combine these two grades.

Internships, also in collaboration with international colleagues, will be proposed during the lectures. Students interested in an internship are invited to contact the instructors for more information. We will be happy to share and discuss potential internship projects