Article ID: | iaor20052557 |
Country: | France |
Volume: | 36 |
Issue: | 1 |
Start Page Number: | 21 |
End Page Number: | 36 |
Publication Date: | Jan 2002 |
Journal: | RAIRO Operations Research |
Authors: | Bampis Evripidis, Knig J.-C., Giroudeau R. |
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communications, and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless