Open Collections

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

Banff International Research Station for Mathematical Innovation and Discovery

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

Mathematics; Computer science; Combinatorics; Theoretical computer science

video/mp4

Author affiliation: Christian-Albrechts-Universität zu Kiel

2016-06-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/58239

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/