Tightness Results for Malleable Task Scheduling Algorithms

Ulrich M. Schwarz
Institut für Informatik
Christian-Albrechts-Universität zu Kiel
Olshausenstraße 40, 24098 Kiel, Germany

Malleable tasks are a way of modelling jobs that can be parallelized to get
a (usually sublinear) speedup. The best currently known approximation
algorithms for scheduling malleable tasks with precedence constraints are 
a) a 2.62-approximation for certain classes of precedence constraints such
as series-parallel graphs [Lepere et al. 2002], and b) a 4.72-approximation
for general graphs via a two-step linear programming approach [Jansen &
Zhang, ISAAC 2005]. 

We show that these rates are tight, i.e. in both settings, there exist
instances that achieve the upper bounds.