L'objectif de ce cours est de présenter les différentes classes de problèmes combinatoires tant au point de vue de leur complexité que de celui de leur approximabilité Cette présentation est faite via l'introduction des notions de réduction polynomiale et de réduction de Turing.
Expérience du responsable dans le domaine de l’UE
Enseignant chaire R. O. CNAM depuis 1995- Responsable Master MOCS du CNAM. Membre de l'equipe Optimisation Combinatoire du laboratoire Cedric. Principaux thèmes de recherche : ordonnancements, packing, optimisation dans les graphes, tomographie discrète.
Réalisations du responsable dans le domaine de l’UE
C. Picouleau, New Complexity Results on Scheduling with Small Communication Delays, Discrete Applied Mathematics 60 (1995) 331-342.
C. Picouleau, Worst-case Analysis of Fast Heuristics for Packing Squares into a Square, Theoretical Computer Science 164 (1996) 59-72.
C. Picouleau, Reconstruction of domino tiling from its two orthogonal projections, Theoretical Computer Science 255 (2001) 437-447.
C. Picouleau, Reconstruction of Convex Polyominoes from Orthogonal Projections of their Contours, Theoretical Computer Science 346 2-3 (2005) 439-454.
M.-C. Costa, D. de Werra, C.Picouleau, Using graphs for some discrete tomography problems, Discrete Applied Math. 154 1 (2006) 35-46.
