Complexité paramétrée et Approximation Polynomiale (CAP)

dernière modif : le 18/12/2023 à 18:40:27
Titre :
Complexité paramétrée et Approximation Polynomiale (CAP)
Section :
Optionnel
État pour cette année :
OPEN
Mots clés :
Algorithmes approchés, complexité paramétrée, algorithmes FPT, noyau
Ects :
2
Responsable :
Cédric Bentz (CNAM/CEDRIC)
Intervenants :
Dimitri Watel (ENSIIE)
Prérequis :

Cours de complexité de base (classes P et NP, algorithmes polynomiaux et pseudo-polynomiaux, etc.)

Objectif :

  1. Apprendre les notions de base en approximation polynomiale, et en conception d'algorithmes approchés.

  2. Apprendre à analyser le ratio d'approximation d'un algorithme approché.

  3. Apprendre les notions de base en complexité paramétrée, et en conception d'algorithmes FPT.

  4. Apprendre les notions de base en calcul de noyau pour les problèmes paramétrés, et en analyse de la taille des noyaux obtenus.\

Contenu / Plan :

  • Panel d'exemples d'algorithmes d'approximation polynomiale sur des problèmes classiques. Classes des problèmes d'optimisation et de leur approximabilité (en particulier PO, NPO, APX, PTAS, FPTAS, EPTAS, AAPX, APX$\infty$, PTAS$\infty$). Relation entre l'appartenance à la classe FPTAS et la NP-complétude au sens fort des problèmes d'optimisation.

  • Approximabilité et programmation linéaire. Conception d'algorithmes d'approximation probabilistes. Technique d'arrondi, arrondi probabiliste, déterminisation, dual fitting et schéma primal-dual pour la conception d'algorithmes approchés.

  • Inapproximabilité, et notion de rapport serré. Réductions préservant les rapports d'approximation, et réductions GAP. Notion et exemples de complétude. Introduction au théorème PCP.

  • Paramétrisation de problèmes de NP. Définition des classes de base en complexité paramétrée : hiérarchie des classes W[t], classes FPT et XP. Notion de FPT-réduction, et conséquences basées sur la W[1]-difficulté du problème de clique. Conception d'algorithmes FPT via les arbres de recherche bornés. Liens avec l'approximation polynomiale, et notamment avec l'existence d'EPTAS.

  • Notion de (calcul de) noyau en complexité paramétrée. Équivalence entre l'existence d'un noyau et celle d'un algorithme FPT. Exemples de calcul de noyaux, quadratiques ou linéaires, pour une sélection de problèmes (transversal minimum, $k$-MAX 3-SAT, $k$-MAX SAT, etc.), à l'aide de règles de réduction. Calcul de noyaux linéaires pour l'existence de certaines structures dans les graphes planaires (des stables, par exemple).

  • Examen.

Bibliographie :

  • Parameterized Complexity, R. Downey et M. Fellows, Springer 1999.

  • Computers and Intractability, M. Garey et D. Johnson, Freeman 2003.

  • Complexity and approximation, Combinatorial optimization problems and their approximability properties de G. Ausiello, P. Crescenzi, G.Gambosi, V. Khan, A. Marchetti-Spaccamela et M.Protasi, édition Springer-Verlag Berlin Heidelberg, 1999. ISBN : 3-540-65431-

  • Approximation algorithms de V. V. Vazirani, édition Springer-Verlag Berlin Heidelberg, 2003. ISBN : 978-3-642-08469-0

  • Approximation polynomiale de problèmes d'optimisation : aspects structurels et opérationnels de B. Escoffier, 2005, http://www.theses.fr/2005PA090065

Liens :
(aucun)
Compétences visées :

Savoir concevoir des algorithmes approchés simples, combinatoires ou à l'aide de techniques de programmation mathématique, et analyser leur ratio d'approximation

Savoir établir des résultats d'inapproximabilité simples (sous certaines hypothèses de complexité).

Savoir concevoir des algorithmes FPT simples, et savoir montrer qu'un problème n'admet pas d'algorithmes FPT (sous certaines hypothèses de complexité).

Savoir calculer des noyaux à l'aide de règles de réduction simples.

Modalités de contrôle :

Examen lors de la dernière séance