# 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

top## How 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). Zbl0944.90022
- 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). Zbl0411.68039
- 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
- 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 ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.