Accès directs

Outils

INFO5119 : CR04: Theory of (Linear) Optimization and Approximation Algorithms

Responsable(s) :
  • Aurelien Garivier
Enseignant(s) :
  • Alantha Newman

Niveau

M2

Discipline

Informatique

ECTS
5.00
Période
1e semestre
Département
Département d'Informatique
Localisation
Site Monod
Année
2026
Langue d'enseignement
Anglais

Public externe (ouverts aux auditeurs de cours)

Informations générales sur le cours : INFO5119

Content objectif


 

  • Instructors: Sophie Huiberts and Alantha Newman
  • Prerequisites: Basic concepts in algorithms, complexity theory, linear algebra and discrete probability.
  • Objective: Approximation algorithms is a widely studied research area in which the goal is to design efficient algorithms with provable guarantees for NP-hard optimization problems. The objective of this course is to study classic and foundational techniques and approaches developed in this research area, as well as to gain familiarity with some recent advances in the field. Topics will include algorithms for linear/convex programming, extracting integer solutions from optimal fractional solutions using tools such as randomized and iterative rounding, and algorithms for classic NP-hard optimzation problems such as the traveling salesman problem.

  • Course Outline: 

    1) Obtaining optimal (fractional) solutions for relaxations.
     

    • This part will cover the basics of linear programming (LP) and the simplex method, including worst-case complexity, Kitahara and Mizuno's upper bound on the running time of the simplex method as well as more modern analysis (e.g., random shadow vertex method). It will also cover practical simplex methods, what they are used for and how they differ from theoretical descriptions.


    2) Obtaining near-optimal integral solutions.

     

    • This part will cover classic approaches for "rounding" fractional solutions for linear and convex programs to obtain provably near-optimal integer solutions. It will cover classic tools such as randomized and iterative rounding of linear programs, primal-dual algorithms, random-hyperplane rounding for semidefinite programs, and recent techniques using LP hierarchies. In some cases, we consider more problem-specific rounding approaches, based on extreme point structure or on other ways of extracting structure from fractional solutions.
    • Some examples of optimization problems we will study are: min and max-cut, clustering and graph partitioning, scheduling, coloring, unique games, traveling salesman problem.

     

  • Evaluation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.
  • Related Resources:

     
    1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys 
       
    2. Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan at UC Berkeley
    3. Approximation Algorithms Traveling Salesman Problems by Vera Traub and Jens Vygen at Universitaet Bonn