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

Abstract

top
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.

How to cite

top

Bampis, 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
  1. 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.  
  2. 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).  
  3. Ph. Chrétienne, E.J. Coffman Jr., J.K. Lenstra and Z. Liu, Scheduling Theory and its Applications. Wiley (1995).  
  4. M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman (1979).  
  5. 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.  
  6. 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 ?

top

You must be logged in to post comments.