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
Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Maximum Independent Set in H-free graphs
Théorie des graphes
Friday 05 October 2018 - 14h30
Salle : 445 - PCRI-N
Edouard BONNET .............................................

A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

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

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................