Talgo (Théorie, ALgorithmes, Graphes et Optimisation)

Talgo est une équipe de recherche du Département d'Informatique de l'École normale supérieure, soutenue par l'ENS et le CNRS. Les thèmes de recherche actuels de l'équipe consistent en le développement d'algorithmes et en la découverte de propriétés structurelles, notamment pour l'optimisation combinatoire et pour des problèmes d'origine géométrique. Nous utilisons des outils de théorie des graphes, combinatoire, probabilités et optimisation.

Nouvelles

• Postes : Post-docs FSMP: contacter Chien-Chung Huang durant le première quinzaine de novembre si vous êtes intéressés par la possibilité d'un post-doc FSMP dans l'équipe Talgo. Date limite de candidature 1er décembre 2017. Début du post-doc à partir d'octobre 2018.
• Claire Mathieu occupe la chaire annuelle "Informatique et sciences numériques" au Collège de France en 2017-2018, avec un cours intitulé Algorithmes, dont la leçon inaugurale aura lieu le 16 novembre 2017 à 18h.
• Vincent Cohen-Addad, ancien doctorant de Talgo, a reçu le prix de thèse Graphes Charles Delorme 2017, le prix de thèse PGMO 2017, et le prix EATCS 2017.
• Nos anciens doctorants : Frederik Mallmann-Trenn est post-doc au MIT ; Hang Zhou est maître de conférences à l'X ; Vincent Cohen-Addad est CR CNRS au laboratoire LIP6 (UPMC); Arnaud de Mesmay est CR CNRS au laboratoire GIPSA-lab (Grenoble)

Séminaire

Membres

Permanents

• Chien-Chung Huang (CR CNRS, responsable)
• Zhentao Li (maître de conférences ENS, en congé 2017-2018)
• Claire Mathieu (DR CNRS, en stage à l'IRIF 2017-2018)
• Tatiana Starikovskaya (maître de conférences ENS)

Post-docs, visiteurs, stagiaires, etc.

• Thang Nguyen (délégation CNRS à l'ENS en 2017-2018)
• Abhinav Srivastav postdoc ENS-Dauphine, 2017-2018
• Nabil Mustafa (visiteur occasionnel, depuis l'automne 2016)
• Kevin Schewior, postdoc DAAD, à partir de juin 2018

Doctorants

• Victor Verdugo (thèse prévue 2018)
• Mathieu Mari (thèse prévue 2020)

Enseignement

Nous intervenons dans les cours Algorithmique et programmation du L3 de l'ENS et Algorithmique et combinatoire des graphes géométriques du MPRI.

Collaborations principales

• with Dauphine (Vangelis Paschos et al.). Project MultiFAC (Multiple Facility Location). PSL funded project. Jan 2017-Dec 2018
• avec Frédéric Magniez et d'autres membres du LIAFA (programme ANR blanc RDAM), jusqu'à Déc 2017.
• avec Philip N. Klein et David Eisenstat, (Medium NSF collaborative grant, 0964037), terminé.
• avec Xavier Goaoc et Martin Tancer (partenariat Hubert Curien Embeds), terminé.

Faits marquants 2017

Distances entre tous les points dans un graphe valué: un algorithme distribué

Chien-Chung Huang, Danupon Nanongkai, et Thatchaphol Saranurak développent un algorithme distribué probabiliste rapide pour calculer les distances entre toutes les paires de noeurs dans un graphe avec poids.

Faits marquants 2016

Recherche locale pour le k-médian dans les graphes planaires et le plan euclidien

Vincent Cohen-Addad, Philip Klein et Claire Mathieu ont démontré que la recherche locale était un schéma d'approximation pour le problème du k-médian dans les graphes planaires et le plan euclidien. Le problème du k-médian est le suivant: étant donné des clients, et des distances dans le plan Euclidien ou définies par des plus courts chemins dans un graphe planaire, positionner k centres de façon à minimiser la somme sur les clients de la distance du client au plus proche centre. L'algorithme de recherche locale améliore une solution en déplaçant quelques-uns des centres de façon itérative. Cette stratégie est quasi-optimale.

Faits marquants 2015

Le plafond de verre dans les réseaux sociaux

DBLP est la base de données recensant toutes les publications de la communauté informatique. Plusieurs dizaines de milliers d’auteurs y sont répertoriés, sur une période couvrant plus de trente ans. Parmi eux, 79% d’hommes. Un pourcentage qui augmente encore lorsqu'on s'intéresse aux auteurs les plus influents : ainsi, plus un chercheur est reconnu, ce qui est évalué par son nombre de coauteurs notamment, plus il y a de chances pour que ce soit un homme. Ce phénomène sociologique est couramment appelé plafond de verre : la barrière invisible mais infranchissable qui empêche les minorités et les femmes d’accéder à des fonctions plus élevées dans le monde professionnel, en dépit de leurs qualifications.

Claire Mathieu et ses collègues Chen Avin, Barbara Keller, Zvi Lotker, David Peleg et Yvonne Pignolet ont étudié ce problème dans un article paru à ITCS 2015: Quelles conditions doivent être réunies au sein d'un réseau social pour qu'un plafond de verre émerge ? Plusieurs hypothèses ont été formulées d'après leurs observations sur le réseau DBLP; les auteurs ont ensuite créé de toutes pièces un réseau social à partir de ces hypothèses, et enfin démontré l'apparition d'un plafond de verre au sein de ce réseau.

Jeux coopératifs

Combien doit-on payer des agents égoïstes pour les faire travailler sur un projet commun nécessitant la participation de tous? La réponse pour les jeux coopératifs est: suffisamment pour qu'aucun petit groupe a intérêt à dévier et travailler ensemble sur quelque chose d'autre qui rapporte plus que ce qu'ils sont payés. Dans le modèle classique de Myerson, les petits groupes qui peuvent se former sont déterminés par un graphe de communication entre les agents.

Zhentao Li et ses collaborateurs Nicolas Bousquet et Adrian Vetta ont présenté à l'ACM Conference on Economics and Computation un résultat améliorant l'écart entre la somme payée et le gain du projet dans le pire jeu. Pour ce faire, ils introduisent un nouveau paramètre de graphe. Pour tout graphe de communication, ils donnent des exemples de jeu où cet ratio est atteint, ce qui montre que leur borne est exacte.

Placement d'installations

Comment disposer des casernes de pompiers dans une ville? Étant donné un ensemble de points P de R^d et un coût de construction, le problème du placement d'installations (facility location) est de produire un ensemble S d' installations de sorte que le coût total de construction plus la somme des distances de chaque client à l'installation la plus proche soit minimal.

Vincent Cohen-Addad et Claire Mathieu, au Symposium on Computational Geometry, analysent les performances de l'algorithme dit de recherche locale -- une heuristique courante et facile d'implémentation pour les problèmes d'optimisation -- pour le problème du placement d'installations. Étant donnée une solution réalisable, l'algorithme de recherche locale répète des opérations d'une certaine classe afin d'améliorer le coût de la solution courante, et ce jusqu'à trouver une solution qu'aucune opération de la classe ne peut améliorer. Ils montrent que cette approche très simple produit une solution d'un coût proche de celui de la solution optimale.

Multicoupe minimale

Étant donné un réseau, comment supprimer un ensemble minimal de connexions pour séparer des paires de terminaux donnés? Le problème de la multicoupe minimale est connu pour être NP-difficile et inapproximable même dans des instances très simples (par exemple quand le réseau est un arbre).

Éric Colin de Verdière, au European Symposium on Algorithms, a montré que le problème était résoluble en temps polynomial si le nombre de paires de terminaux était borné et si le graphe était planaire (ou plus généralement dessinable sans croisement sur une surface fixée). Dans le cas planaire, le résultat était connu depuis plus de vingt ans dans le problème plus restreint de multiway cut; pour cette généralisation, des méthodes empruntées à la topologie algorithmique s'avèrent nécessaires.