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

Abstract

top
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 (unless ). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time -approximation algorithm with 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 - 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 &lt; 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 &lt; 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. [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. [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. [3] Ph. Chrétienne, E.J. Coffman Jr., J.K. Lenstra and Z. Liu, Scheduling Theory and its Applications. Wiley (1995). Zbl0873.90049MR1376605
  4. [4] M.R. Garey and D.S. Johnson, Computers and Intractability, a Guide to the Theory of -Completeness. Freeman (1979). Zbl0411.68039MR519066
  5. [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. [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 ?

top

You must be logged in to post comments.