# On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

Evripidis Bampis; R. Giroudeau; J.-C. König^{[1]}

- [1] LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France

RAIRO - Operations Research - Recherche Opérationnelle (2002)

- 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 - Recherche Opérationnelle 36.1 (2002): 21-36. <http://eudml.org/doc/245145>.

@article{Bampis2002,

abstract = {We consider the unit execution time unit communication time ($\!$UET-UCT$\!$) scheduling model with hierarchical communications [1], 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 $\{\mathcal \{P\}\}=\{\mathcal \{NP\}\}$). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time $\rho $-approximation algorithm with $\rho < 7/6$ for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.},

affiliation = {LIRMM, Université de Montpellier II, UMR 5506 du CNRS, 161 rue Ada, 34392 Montpellier Cedex 5, France},

author = {Bampis, Evripidis, Giroudeau, R., König, J.-C.},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {scheduling; hierarchical communications; non-approximability},

language = {eng},

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/245145},

volume = {36},

year = {2002},

}

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 - Recherche Opérationnelle

PY - 2002

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 communications [1], 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 ${\mathcal {P}}={\mathcal {NP}}$). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time $\rho $-approximation algorithm with $\rho < 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-approximability

UR - http://eudml.org/doc/245145

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.90022MR1665416
- [3] Ph. Chrétienne, E.J. Coffman Jr., J.K. Lenstra and Z. Liu, Scheduling Theory and its Applications. Wiley (1995). Zbl0873.90049MR1376605
- [4] M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of $\mathrm{\mathcal{N}\mathcal{P}}$-Completeness. Freeman (1979). Zbl0411.68039MR519066
- [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.90044MR558574
- [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.90083MR1306216

## NotesEmbed ?

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