Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover - Université d'Évry Access content directly
Theses Year : 2011

Approximation Algorithms with Low Memory Capacities for Large Graphs Processing : the Vertex Cover Problem

Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover

Abstract

We are interested to an optimization problem on graphs (the Vertex Cover) in a very specific context: the huge instances of data. We defined a treatment model based on constraints linked to the limited amount of memory, model for which properties comes from several existing models in the litterature (online, streaming...). We studied several algorithms suitable to this model: we analyzed, first theoretically, the quality of their solutions and their complexities (in worst and average case). We then conducted an experimental study on very large graphs.
Nous nous sommes intéressés à un problème d'optimisation sur des graphes (le Vertex Cover) dans un contexte de traitement bien particulier : celui des grandes instances de données. Nous avons défini pour cela un modèle de traitement basé sur des contraintes liées principalement à la quantité de mémoire limitée, modèle qui reprenait des propriétés issues de plusieurs modèles existants dans la littérature (online, streaming...). Nous avons étudié plusieurs algorithmes adaptés à ce modèle : nous avons analysé, tout d'abord de façon théorique, la qualité de leurs solutions ainsi que leurs complexités (en pire cas et en moyenne). Nous avons ensuite mené une étude expérimentale sur de très gros graphes.
Fichier principal
Vignette du fichier
rc-memoire.pdf (1.29 Mo) Télécharger le fichier
rc-slides.pdf (1.52 Mo) Télécharger le fichier
Format : Other
Loading...

Dates and versions

tel-00677774 , version 1 (09-03-2012)

Identifiers

  • HAL Id : tel-00677774 , version 1

Cite

Romain Campigotto. Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes : le problème du Vertex Cover. Recherche opérationnelle [math.OC]. Université d'Evry-Val d'Essonne, 2011. Français. ⟨NNT : ⟩. ⟨tel-00677774⟩
307 View
692 Download

Share

Gmail Facebook X LinkedIn More