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

M. Bouznif and R. Giroudeau

Advances in Operations Research, 2011, vol. 2011, 1-20

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 𠑂 ( 𠛿 2 ) -approximation algorithm for the makespan minimization on processor networks with diameter 𠛿 .

Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/AOR/2011/476939.pdf (application/pdf)
http://downloads.hindawi.com/journals/AOR/2011/476939.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlaor:476939

DOI: 10.1155/2011/476939

Access Statistics for this article

More articles in Advances in Operations Research from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().