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).  Zbl0944.90022
  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).  Zbl0411.68039
  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.  Zbl0411.90044
  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.  Zbl0816.90083

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.