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
Journal Articles Advances in Operations Research Year : 2011

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

Abstract

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
Origin Publisher files allowed on an open archive

Dates and versions

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

Licence

Identifiers

Cite

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⟩
124 View
69 Download

Altmetric

Share

More