Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GraphComb
Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes
Romain CAMPIGOTTO

01 February 2013, 10h30 - 01 February 2013, 11h30
Salle/Bat : 475/PCRI-N
Contact :

Activités de recherche :

Résumé :
Lorsque l’on traite de façon classique un problème d’optimisation
sur un graphe, celui-ci est le plus souvent disponible dans sa totalité
sur la machine de traitement : il peut être modifié, mis à jour (les
sommets peuvent être marqués, les arêtes supprimées, etc.) et la
solution peut être conservée en mémoire. Cependant, de plus en plus
d’applications produisent des quantités de données qui sont trop
importantes et ne qui peuvent pas être stockées ni traitées dans ce
modèle.

Dans les travaux que nous avons menés, nous nous sommes intéressés en
particulier au problème du Vertex Cover, dans un contexte de traitement
de grands graphes. A la NP-complétude intrinsèque est ajoutée la
difficulté de manipuler les graphes avec des contraintes sévères
(principalement liées à la quantité restreinte de mémoire
disponible).
Nous avons défini un modèle de traitement regroupant certaines
propriétés de plusieurs modèles existants dans la littérature :
_streaming_, _online_, _I/O-efficient_, etc.

Nous avons dans un premier temps étudié trois algorithmes
d'approximation _memory-efficient_ (ils utilisent un espace mémoire en
_O(log n)_ bits). Nous avons analysé leurs performances en terme de
qualité de solution et de complexité, en pire cas et en moyenne.

Nous nous sommes ensuite intéressés à d'autres algorithmes qui
utilisent un espace mémoire de _n_ bits. Nous avons montré qu'il
pouvait être très mauvais (même en moyenne) dès lors que leur espace
mémoire disponible était plus petit que _n_ bits.

Par la suite, nous avons mené une étude expérimentale sur de très
gros graphes (de l'ordre de plusieurs milliards de sommets et
d'arêtes). Cette étude nous a permis de montrer qu'en pratique, les
algorithmes _memory-efficient_ étaient mieux adaptés pour traiter de
grands graphes.

Pour en savoir plus : http://www-complexnetworks.lip6.fr/~campigotto/
Séminaires
Resilient PDE solving approaches for exascale comp
Calcul à haute performance
Tuesday 29 May 2018 - 10h30
Salle : 465 - PCRI-N
Paul Mycek .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 25 May 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

TBA
Algorithmique distribuée
Wednesday 02 May 2018 - 10h30
Salle : 465 - PCRI-N
Evangelos Bampas .............................................

Mariage stable auto-stabilisant et distribué
Théorie des graphes
Friday 13 April 2018 - 14h30
Salle : 445 - PCRI-N
Marie Laveau .............................................

Modélisation et implémentation du produit de matri
Calcul à haute performance
Wednesday 11 April 2018 - 10h30
Salle : 465 - PCRI-N
Thomas Lambert .............................................