Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Advances in Operations Research Année : 2011

Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks

Résumé

We investigate complexity and approximation results on a processor networks where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no heuristic with a performance guarantee smaller than 4/3 for makespan minimization for precedence graph on a large class of processor networks like hypercube, grid, torus, and so forth,with a fixed diameter δ ∈ . We extend complexity results when the precedence graph is a bipartite graph. We also design an efficient polynomial-time O δ2 -approximation algorithm for the makespan minimization on processor networks with diameter δ.
Fichier principal
Vignette du fichier
476939.pdf (2.21 Mo) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

lirmm-00605652 , version 1 (25-05-2021)

Licence

Identifiants

Citer

Marwane Bouznif, Rodolphe Giroudeau. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research, 2011, 2011, pp.#476939. ⟨10.1155/2011/476939⟩. ⟨lirmm-00605652⟩
126 Consultations
78 Téléchargements

Altmetric

Partager

More