Non-approximability Results for the Hierarchical Communication Problem with a Bounded Number of Clusters

International audienceWe study the hierarchical multiprocessor scheduling problem with a constant number of clusters. We show that the problem of deciding whether there is a schedule of length three for the hierarchical multiprocessor scheduling problem is NP \mathcal{N}\mathcal{P} -complete even for bipartite graphs i.e. for precedence graphs of depth one. This result implies that there is no polynomial time approximation algorithm with performance guarantee smaller than 4/3 (unless P = NP \mathcal{P} = \mathcal{N}\mathcal{P}). On the positive side, we provide a polynomial time algorithm for the decision problem when the schedule length is equal to two, the number of clusters is constant and the number of processors per cluster is arbitrary