Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks
Joint Authors
Source
Advances in Operations Research
Issue
Vol. 2011, Issue 2011 (31 Dec. 2011), pp.1-20, 20 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-06-21
Country of Publication
Egypt
No. of Pages
20
Main Subjects
Information Technology and Computer Science
Abstract EN
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 δ.Erratum to “Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks”dx.doi.org/10.1155/2012/543215
American Psychological Association (APA)
Bouznif, M.& Giroudeau, R.. 2011. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research،Vol. 2011, no. 2011, pp.1-20.
https://search.emarefa.net/detail/BIM-474676
Modern Language Association (MLA)
Bouznif, M.& Giroudeau, R.. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research No. 2011 (2011), pp.1-20.
https://search.emarefa.net/detail/BIM-474676
American Medical Association (AMA)
Bouznif, M.& Giroudeau, R.. Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks. Advances in Operations Research. 2011. Vol. 2011, no. 2011, pp.1-20.
https://search.emarefa.net/detail/BIM-474676
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-474676