ON THE HARDNESS OF APPROXIMATING THE UET-UCT SCHEDULING PROBLEM WITH HIERARCHICAL COMMUNICATIONS

Abstract. We consider the unit execution time unit communication time (UET-UCT) schedulingmodelwith hierarchical communications [1], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polyno-mial time approximation algorithm with performance guarantee smaller than 5=4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time -approximation algorithm with < 7=6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines