Article contents
On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
Published online by Cambridge University Press: 15 July 2002
Abstract
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], 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. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2002
References
- 3
- Cited by