The complexity of short schedules for uet bipartite graphs
The complexity of short schedules for uet bipartite graphs
We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].
On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communications [1], 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 (unless ). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time -approximation algorithm with for the...
On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
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 (unless ). This result is an extension of the result of Hoogeveen [CITE] who proved that there is no polynomial time -approximation algorithm with for the...
Page 1