BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

A Fully Polynomial (3/2 + ∈)-Approximation for Scheduling Monotone Moldable Jobs Land, Felix


A moldable job is a job that can be executed on an arbitrary number of processors, and whose processing time depends on the number of processors allotted to it. We consider the problem of scheduling monotone moldable jobs to minimize the makespan. Most existing approximation algorithms have running time polynomial in the number n of jobs and the number m of processors. We argue that for compact input encodings, such running times are actually exponential in the input size, and that a fully polynomial algorithm has a running time polynomial in n and logm. The best known approximation algorithm with such a running time is due to Mounie, Rapine, and Trystram and achieves approximation ratiop3 +. Another algorithm, also due to Mounie, Rapine, and Trystram, has approximation ratio (3/2 + ∈), but has running time O(nm). We describe different techniques to improve the running time of the latter to polynomial in n and logm. In particular, we show how to solve a knapsack problem with n items and capacity m in time O(n2log m) when items larger than b = (1) can be compressed by a factor 1

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International