Startseite > Publikationen > Publikationen


Leonardi, Stefano;Marchetti-Spaccamela, Alberto;Meyer auf der Heide, Friedhelm:

Scheduling Against an Adversarial Network.

In: Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), S. 151-158, Jun. 2004


Using idle times of the processors is a well-known
approach to run coarse grained parallel algorithms for extremely
complex problems. We present on-line algorithms for scheduling
the processes of a parallel application that is known off-line
on a dynamic network in which the idle times of the processors
are dictated by an adversary. We also take communication and synchronization
costs into account.

Our first contribution consists of a formal model to restrict the adversary
in a reasonable way.
We then show a constant factor approximation for the off-line scheduling
problem. As this problem has to take communication cost into account,
it can be seen as a generalization of many NP-hard parallel machine scheduling problems. Finally, we present on-line algorithms for different models with constant or with nearly constant
competitive ratio.




author = {Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Meyer auf der Heide, Friedhelm},
title = {Scheduling Against an Adversarial Network},
booktitle = {Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004)},
pages = {151-158},
month = jun,
year = {2004},

BibTeX in die Zwischenablage kopieren