Agrégation de ressources avec contrainte de distance : applications aux plateformes de grande échelle.
LARCHEVÊQUE, Hubert
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
LARCHEVÊQUE, Hubert
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
< Réduire
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Langue
fr
Thèses de doctorat
École doctorale
Mathématiques, Sciences et Technologies de l'Information (Informatique)Résumé
Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande ...Lire la suite >
Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.< Réduire
Résumé en anglais
During this Ph. D. we introduced two problems, respectively Bin Covering under Distance Constraints (BCCD in French) and Bin Packing under Distance Constraints (BPCD in French). Both problems find their applications in ...Lire la suite >
During this Ph. D. we introduced two problems, respectively Bin Covering under Distance Constraints (BCCD in French) and Bin Packing under Distance Constraints (BPCD in French). Both problems find their applications in large scale networks, like the Internet. The study of those problems in general metric spaces revealed that it is impossible to work in such a general framework with using resource augmentation, that allows solutions built by one of our algorithms to be less constrained than the optimal solution they are compared to. We prove both interesting approximation results, and that without using resource augmentation those problem are hard to tackle. In this work we were also interested in tools aiming at embedding large scale networks aimed by our applications into well described metric spaces. Thus we studied our problems in some specific metric spaces, generated by some of those tools, namely Vivaldi and Sequoia.< Réduire
Mots clés
Bin Packing
Bin Covering
algorithmes d'approximation
augmentation de ressources
algorithmes distribués
structure de données probabiliste
réseaux de grande échelle
plongement d'Internet
Mots clés en anglais
approximation algorithms
resource augmentation
distributed algorithms
probabilistic data structures
large scale networks
embedding of the Internet
Origine
Importé de halUnités de recherche