Lower and upper bounds for online algorithms with advice
Marc P. Renault · 2014
Les algorithmes en ligne fonctionnent dans un contexte ou l'entree est revele au fur et a mesure du temps; chaque morceau revele est appele une demande. Apres reception de chaque demahde, les algorithmes en ligne doivent prendre une action avant que la prochaine demande soit revelee, c'est-a-dire que les algorithmes en ligne doivent prendre une decision irrevocable basee sur les demandes deja revelees sans aucune connaissance des demandes a venir. Le but est d'optimiser une fonction de cout dependante de l'entree. L'analyse competitive est la methode standard utilisee pour analyser la qualite des algorithmes en ligne. Le ratio competitif est un ratio de pire cas, parmi toutes les sequences de demande finis, entre la performance de l'algorithme en ligne contre un algorithme optimal hors ligne pour la meme sequence. Le ratio competitif compare la performance d'un algorithme sans aucune connaissance de l'avenir contre un algorithme en pleine connaissance de l'avenir. Car l'absence totale de connaissance de l'avenir n'est souvent pas une hypothese raisonnable, des modeles ont ete proposes, appeles algorithmes en ligne avec conseil, qui donne les algorithmes en ligne l'acces a une quantite quantifiee des connaissances de l'avenir. L'interet de ce modele est d'examiner comment le ratio competitif change en fonction de la quantite de conseil. Dans cette these, il est presente des bornes superieures et inferieures dans ce modele pour des problemes en ligne classiques, tels que le probleme de la k-serveur, de bin packing, de dual bin packing (sac a dos multiple), d'ordonnancement sur m machines identiques, du tampon de reordonnancement et de la mise a jour de la liste.