On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
Evripidis Bampis; R. Giroudeau; J.-C. König
RAIRO - Operations Research (2010)
- Volume: 36, Issue: 1, page 21-36
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topBampis, Evripidis, Giroudeau, R., and König, J.-C.. "On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications." RAIRO - Operations Research 36.1 (2010): 21-36. <http://eudml.org/doc/105259>.
@article{Bampis2010,
abstract = {
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation.
We prove that there is no polynomial time approximation algorithm
with performance guarantee smaller than 5/4 (unless P = NP).
This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm
with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication
delays and an unrestricted number of identical machines.
},
author = {Bampis, Evripidis, Giroudeau, R., König, J.-C.},
journal = {RAIRO - Operations Research},
keywords = {Scheduling; hierarchical communications; non-approxima bility.; scheduling; non-approximability},
language = {eng},
month = {3},
number = {1},
pages = {21-36},
publisher = {EDP Sciences},
title = {On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications},
url = {http://eudml.org/doc/105259},
volume = {36},
year = {2010},
}
TY - JOUR
AU - Bampis, Evripidis
AU - Giroudeau, R.
AU - König, J.-C.
TI - On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 36
IS - 1
SP - 21
EP - 36
AB -
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation.
We prove that there is no polynomial time approximation algorithm
with performance guarantee smaller than 5/4 (unless P = NP).
This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm
with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication
delays and an unrestricted number of identical machines.
LA - eng
KW - Scheduling; hierarchical communications; non-approxima bility.; scheduling; non-approximability
UR - http://eudml.org/doc/105259
ER -
References
top- E. Bampis, R. Giroudeau and J.C. König, Using duplication for multiprocessor scheduling problem with hierarchical communications. Parallel Process. Lett.10 (2000) 133-140.
- B. Chen, C.N. Potts and G.J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability, Technical Report Woe-29. TU Graz (1998).
- Ph. Chrétienne, E.J. Coffman Jr., J.K. Lenstra and Z. Liu, Scheduling Theory and its Applications. Wiley (1995).
- M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman (1979).
- R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministics sequencing and scheduling theory: A survey. Ann. Discrete Math.5 (1979) 287-326.
- J.A. Hoogeveen, J.K. Lenstra and B. Veltman. Three, four, Five, six, or the complexity of scheduling with communication delays. Oper. Res. Lett.16 (1994) 129-137.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.