Lecture Notes in Computer Science, 2008, Volume 4967/2008, 1059-1067, DOI: 10.1007/978-3-540-68111-3_112

Tightness Results for Malleable Task Scheduling Algorithms

Ulrich M. Schwarz

View Related Documents

Abstract

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) 2.62-approximation for certain classes of precedence constraints such as series-parallel graphs [1], and b) 4.72-approximation for general graphs via linear programming [2]. We show that these rates are tight, i.e. there exist instances that achieve the upper bounds.

Fulltext Preview

Image of the first page of the fulltext document