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

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 -