Cette thèse concerne l'utilisation de l'interaction entre un algorithme et un expert pour la résolution de problèmes complexes, typiquement NP-difficiles. Plusieurs définitions de l'expert sont possibles. L'objectif étant d'obtenir des algorithmes dont les performances sont garanties, ce travail est centré sur les interactions avec un expert de type "oracle", plutôt que "humain". Ainsi, on s'intéresse à des compromis entre performance, coût (typiquement temps d'exécution), et quantité d'information donnée par l'oracle. Le premier objectif de cette thèse est de comprendre quel est l'état de l'art des différentes techniques interactives dans différents domaines (algorithmique distribuée et online, complexité, optimisation combinatoire). Le second objectif est centré sur l'optimisation combinatoire, et plus particulièrement les problèmes d'ordonnancement et d'empaquetage. Nous proposons un formalisme interactif pour le contexte des problèmes d'optimisations (offline). Le but est de montrer en quoi ce formalisme facilite la conception d'algorithmes d'approximation, en le situant par rapport aux techniques classiques de conception de schémas d'approximation, et en l'utilisant pour fournir de nouveaux résultats sur des problèmes d'ordonnancement et d'empaquetage. Nous avons principalement abordé deux problèmes : le "discrete Resource Sharing Scheduling Problem ($dRSSP$)" et le problème du "Multiple Strip Packing" ($MSP$). Le $dRSSP$ est un problème d'hybridation d'algorithmes. Etant donné un ensemble d'algorithmes (appelé un "portfolio"), un nombre fini de ressources (des processeurs par exemple), et un ensemble représentatif d'instances (appelé "benchmark"), le but est de distribuer ces ressources aux algorithmes afin de minimiser le temps nécessaire à la résolution de toutes les instances du benchmark, en exécutant les algorithmes en parallèle selon le modèle dit du "space sharing" . Nous avons étudié l'impact de plusieurs questions à poser à l'oracle, ainsi que comment communiquer efficacement avec ce dernier (signifiant que la réponse de l'oracle est courte), aboutissant à plusieurs schémas d'approximation. Le $MSP$ est une extension du problème célèbre du "Strip Packing" consistant à placer des rectangles dans un nombre fixé de boîtes, en minimisant la hauteur atteinte. Nous avons fourni plusieurs algorithmes/schémas d'approximation pour différentes variantes de ce problème, dans lesquelles les boîtes ont des largeurs égales/différentes, ou les rectangles doivent être placés de façon "continue" ou non (correspondant alors à un problème classique d'ordonnancement de tâches parallèles). D'une manière générale l'utilisation de l'interactivité permet d'isoler la difficulté des problèmes, et donc de les étudier différemment.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00543195 |
| Date | 15 October 2010 |
| Creators | Bougeret, Marin |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0023 seconds