Non-approximability Results for the Hierarchical Communication Problem with a Bounded Number of Clusters - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2002

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

Eric Angel
  • Function : Author
  • PersonId : 855946
Evripidis Bampis
  • Function : Author
  • PersonId : 855947
Rodolphe Giroudeau

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.
Fichier principal
Vignette du fichier
ark__67375_HCB-MBLD9S0Z-Z.pdf (156.03 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00268636 , version 1 (18-09-2019)

Identifiers

Cite

Eric Angel, Evripidis Bampis, Rodolphe Giroudeau. Non-approximability Results for the Hierarchical Communication Problem with a Bounded Number of Clusters. Euro-Par: European Conference on Parallel Processing, Aug 2002, Paderborn, Germany. pp.217-224, ⟨10.1007/3-540-45706-2_28⟩. ⟨lirmm-00268636⟩
94 View
86 Download

Altmetric

Share

Gmail Facebook X LinkedIn More