[clustering]

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)

Membres

image20170918_161756085_2.jpg   image20170918_161742412.jpg

Permanents

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

Anciens membres: Frederik Mallmann-Trenn (doctorant 2014-2017) É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).

Visiteurs: Paweł Gawrychowki (2 semaines, 2017) - Piotr Krysta (2017) - Naonori Kakimura (2017) - Anna Adamaszek (2017) - Neal E. Young (professeur invité, printemps 2017) - Dieter van Melkebeek (professeur invité, automne 2016) - Philip Klein (été 2016) - 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)...

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)...

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)

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.

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