Curriculum M1 MPRI at ENS Paris-Saclay

APSA: AProximation and String Algorithms

Description: This advanced algorithms course aims to introduce students to the fundamentals of string algorithms, approximation algorithms, and linear programming. The concepts covered include the design of efficient algorithms for classic problems and approximation problems, as well as applications of linear programming techniques.

Outline:

  1. Approximation Algorithms I: vertex cover, set cover, subset sum
  2. Approximation Algorithms II: metric TSP, knapsack, load balancing
  3. Approximation Algorithms III: LP relaxation, weighted vertex/set cover, MAX-CUT
  4. Approximation Algorithms IV: k-center, local search
  5. String Algorithms I: Morris–Pratt, Knuth–Morris–Pratt
  6. String Algorithms II: Simon's algorithm, Boyer–Moore
  7. String Algorithms III: two-way string matching


References:

  • Serge Haddad. Algorithmique 2. Lecture notes, 2021.
  • Danièle Beauquier, Jean Berstel et Philippe Chrétienne. Eléments d’algorithmique. Masson, 1992
  • Vijay V. Vazirani. Approximation Algorithms. Heidelberg : Springer, 2003
  • Web site of instructors and ecampus.