Séminaires : Séminaire Combinatoire, Optimisation, et Interactions

The purpose of this seminar is to foster exchanges within the CO team of IMJ-PRG, and also with the surrounding scientific community. As such, its range of topics should be quite broad. We initially plan one or two sessions per month.

Ce séminaire a pour but de développer les échanges au sein de l'équipe Combinatoire et Optimisation, et avec la communauté scientifique environnante. Ses thèmes seront donc larges. Nous prévoyons un rythme initial de une à deux séances par mois.

Certains algorithmes d'optimisation ont un temps d'exécution qui va croissant avec le nombre de contraintes affines à respecter. Pour accélérer la recherche d'un minimiseur x* sur un polytope P, il est parfois bien plus rapide de traduire le problème sur une extension affine Q de P, d'y touver un minimiseur z* qui donnera un x* sur P par projection. Cela a motivé la définition de la "complexité d'extension" d'un polytope P donné (plus petite taille d'une extension affine de P). Après avoir défini cette notion, nous l'illustrerons par quelques exemples : polytope de Birkhoff, polytope de corrélations, permutoèdre, polygones, polytope des matchings (d'un graphe G). En se restreignant aux extensions Q qui "respectent" les symétries de P, on obtient la notion de complexité d'extension symétrique. On donnera diverses majorations et minorations connues pour les exemples présentés, et des questions ouvertes.