Pour plus d'information sur P||Cmax (preuve de NP-complétude, borne de Graham, etc.) vous pouvez vous rapporter au chapitre 7 Scheduling du livre Parallel Algorithms par H. Casanova, A. Legrand, et Y. Robert chez CRC Press ou pour une version française au livre Algorithmique parallèle : cours et exercices corrigés par A. Legrand et Y. Robert chez Dunod (tous deux sont disponibles à la bibliothèque de l'ENS).
Cours 3: lundi 5 novembre, 16h
Fin de la 2-approximation de R||Cmax (voir notes du cours précédent)
Quelques questions qui m'ont été posées
à propos du DM:
Pour la question 2, je demande simplement comment
prédire les performances de calculs lorsque les transferts
suivants ont lieu simultanément: A envoie des
données à B et A envoie des données à
C.
Pour la question 3, il suffit de donner une (ou plusieurs)
référence(s) à un (des) résultat(s) vu(s) en
cours, éventuellement en le(s) justifiant.
Ce cours est inspiré du chapitre "Algorithmic Game Theory and Scheduling" dans le livre "Handbook of Approximation Algorithms and Metaheuristics", (éditeur T. F. Gonzales, Chapman & Hall/CRC). Ce livre est disponible à la bibliothèque de l'ENS Lyon (espace Laurent Schwartz, cote I.2.6/GONZ). Je peux en fournir des copies si besoin.