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

• Carola Doerr
• Christoph Dürr

This course will be held in English.

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

5.12.2018 [Carola] Introduction to heuristic search, motivation, applications, the role of mathematical investigations and a fundamental “theory dilemma”. Discussion of the course project.

12.12.2018 [Carola] Analysis of iterative optimization heuristics: performance measures, tools and techniques, hot topics, algorithm-specific performance bounds

19.12.2018 [Carola] The parameter selection problem: offline vs. online algorithm configuration

9.1.2019 [Carola] Black-box complexity: lower bounds for selected classes of iterative optimization heuristics

16.1.2019 [Christoph] Local search : 2-approximation for scheduling with precedence relations, Schöning’s randomized local search for 3-SAT, local search for k-median. en français: notes 1, in english simpler proof by Gupta and Tangwongsan'2008

23.1.2019 [Christoph] degree constrained minimum spanning tree, Williamson, Shmoys: The Design of Approximation Algorithms page 49, section 2.6 then page 243, section 9.3.

30.1.2019 [Christoph] Markov Chain Monte Carlo search. If needed introduction to Markov and Chebychev inequalities. Markov chains light, and heavy introduction. Application to lozenge tilings

6.2.2019 (no lecture, deadline for submitting the documentation of the course project/homework)

13.2.2019 [Carola+Christoph] Project/Homework presentations, discussions

20.2.2019 (no lecture)

6.3.2019 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