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

Eric Angel 1 Evripidis Bampis 1 Rodolphe Giroudeau 2
2 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We 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.
Type de document :
Communication dans un congrès
EuroPar'2002: 8th International Conference on Parallel Processing, Aug 2002, Paderborn, Germany. pp.217-224, 2002, LNCS. 〈10.1007/3-540-45706-2_28〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00268636
Contributeur : Christine Carvalho de Matos <>
Soumis le : mardi 1 avril 2008 - 09:28:13
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

Collections

Citation

Eric Angel, Evripidis Bampis, Rodolphe Giroudeau. Non-approximability Results for the Hierarchical Communication Problem with a Bounded Number of Clusters. EuroPar'2002: 8th International Conference on Parallel Processing, Aug 2002, Paderborn, Germany. pp.217-224, 2002, LNCS. 〈10.1007/3-540-45706-2_28〉. 〈lirmm-00268636〉

Partager

Métriques

Consultations de la notice

52