On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

0.00 Avg rating0 Votes
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: , ,
Abstract:

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 P=NP). This result is an extension of the result of Hoogeveen et al. 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.

Reviews

Required fields are marked *. Your email address will not be published.