Talgo (Topologie, 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. Nous développons des algorithmes pour l'optimisation combinatoire et pour des problèmes d'origines géométrique et topologique.
[double torus]

Membres

Permanents

Doctorants

Post-docs, visiteurs, et stagiaires

  • Dieter van Melkebeek (visiteur, automne 2016)
  • Gil Kalai (visiteur, novembre-décembre 2016)
Anciens membres: Éric Colin de Verdière (doctorant et CR CNRS, 2000-2016) - Salman Parsa (post-doc, 2015-2016) - Vincent Cohen-Addad (doctorant, 2013-2016) - Varun Kanade (post-doc, 2014-2015) - Hang Zhou (doctorante, 2012-2015) - Arnaud de Mesmay (doctorant, 2011-2014) - Alfredo Hubard (post-doc, 2012-2013) - Michel Pocchiola (MdC ENS, ?-2009) - Vincent Pilaud (doctorant, 2007-2009) - Luc Habert (doctorant, 2003-2009) - Laurent Rineau (doctorant, 2002-2007) - Pierre Angelier (doctorant, 1998-2002).

Anciens visiteurs: Daniel Kral' (professeur invité, avril 2016) - Bojan Mohar (professeur invité, mai 2016) - Chris Schwiegelshohn (doctorant visiteur, févr.-avr. 2016) - Zvi Lotker (chercheur invité, 2014-2015) - Philip Klein (juillet 2015) - Reut Levi (post-doc, nov 2014-2015) - Chien-Chung Huang (juin 2015) - Sergio Cabello (professeur invité, oct. 2014) - Alon Ardenboim (doctorant stagiaire, août-oct. 2014) - Ioannis Milis (professeur invité, oct. 2014) - Valerie King (professeur invité, mai-juin 2014) - Benjamin A. Burton (professeur invité, nov-déc. 2013) - Sampath Kannan (professeur invité, juin-juil. 2013) - Thomas Sauerwald (sept. 2012, avril-mai 2013) - Jeff Erickson (nov. 2011 et mars 2012) - Menelaos Karavelas (déc. 2011) - Claire Mathieu (mars 2011) - Jaroslav Nesetril (mai 2009) - Ioannis Emiris (févr. et mars 2009) - Micha Sharir (oct. 2008) - Francisco Santos (juin 2008) - Herbert Edelsbrunner (mai 2007) - Günter Rote (sept. 2005) - Jack Snoeyink (avr. 2003) - Ileana Streinu (mars 2003) - Gert Vegter (mars 1999)...

Anciens stagiaires: Thomas Magnard (stagiaire de M2, mars-juillet 2016) - Esteban Salgado (stagiaire de M1, mars-juillet 2016) - Enguerrand Prébet (stagiaire de L3, mai-juillet 2016) - Nick Gaya (Stagiaire de Brown, juin-juillet 2013), Ambroise Marigot (Stagiaire M1, sept.-nov. 2012) - Arnaud de Mesmay (Stagiaire M2, mars-août 2011) - Alexandre Boulc'h (Stagiaire M1, avril-août 2010) - Kshitij Bansal (Stagiaire L3, mai-juin 2009) - Julien Ferté (Stagiaire M1, mars-juillet 2008) - Hrushikesh Tilak (Stagiaire L3, mai-juin 2008) - Preyas Popat (Stagiaire L3, mai-juin 2008) - Shreevasta Rajagopalan (Stagiaire L3, mai-juin 2007) - Laurent Jouhet (Stagiaire M2, mars-août 2007) - Vincent Pilaud (Stagiaire M2, mars-août 2005) - Constin Vilcu (Stagiaire M2, mars-août 2004)...

Directions de recherche actuelles

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 des problèmes d'origine géométrique et topologique, et pour l'optimisation combinatoire. Nous utilisons des outils de topologie algébrique, combinatoire, probabilités et optimisation. En terme de communautés, les principaux domaines sont l'algorithmique discrète (SODA) et la géométrie algorithmique (SoCG), avec des liens en combinatoire et théorie des graphes. Quatre directions de recherche sont actuellement poursuivies :
  • l'algorithmique des graphes plongés: algorithmes d'approximation pour les graphes planaires; algorithmes pour des problèmes topologiques dans les graphes sur les surfaces;
  • algorithmes d'approximation et techniques d'optimisation combinatoire;
  • algorithmes en ligne pour des problèmes de graphes;
  • des problèmes de géométrie combinatoire avec une composante topologique.

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.

Annonces

Arnaud de Mesmay, ancien doctorant de l'équipe, devient chargé de recherche CNRS, affecté au laboratoire GIPSA-lab (Grenoble) à compter d'octobre 2015.

Hang Zhou, ancienne doctorante de l'équipe, est en post-doctorat à MPI Saarbrücken (Allemagne) à compter de septembre 2015.

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.

Collaborations principales

Contact


Département d'Informatique - École normale supérieure
45, rue d'Ulm
75230 Paris Cedex 05 - France
Bureaux: Hauts du DI (esc. A, 3ème étage)

 
Webmaster: webdi[@]di[.]ens[.]fr.