loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04)
General Non-Approximability Results in Presence of Hierarchical Communications
Cork, Ireland
July 05-July 07
ISBN: 0-7695-2210-6
ASCII Text
x 
 
R. Giroudeau, J. C. K?nig, "General Non-Approximability Results in Presence of Hierarchical Communications," Parallel and Distributed Computing, International Symposium on, pp. 312-319, Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/ISPDC.2004.27,
author = {R. Giroudeau and J. C. K?nig},
title = {General Non-Approximability Results in Presence of Hierarchical Communications},
journal ={Parallel and Distributed Computing, International Symposium on},
volume = {0},
year = {2004},
isbn = {0-7695-2210-6},
pages = {312-319},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPDC.2004.27},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Computing, International Symposium on
TI - General Non-Approximability Results in Presence of Hierarchical Communications
SN - 0-7695-2210-6
SP312
EP319
A1 - R. Giroudeau,
A1 - J. C. K?nig,
PY - 2004
KW - hierarchical communications
KW - scheduling
KW - nonapproximability
VL - 0
JA - Parallel and Distributed Computing, International Symposium on
ER -
 
R. Giroudeau, LIRMM
J. C. K?nig, LIRMM
We investigate the problem of minimizing the makespan (resp. the sum of the completion time) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in connected clusters. We propose general non-approximability results for the case where all the tasks of the precedence graph have unit execution times, where the multiprocessor is composed of an unrestricted number of machines with ι ≥ 4 identical processors each.
Index Terms:
hierarchical communications, scheduling, nonapproximability
Citation:
R. Giroudeau, J. C. K?nig, "General Non-Approximability Results in Presence of Hierarchical Communications," ispdc, pp.312-319, Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.