An improved approximation algorithm for scheduling monotonic moldable tasks

We are concerned with the problem of scheduling monotonic moldable tasks on identical processors to minimize the makespan. We focus on the natural case where the number m of processors as resources is fixed or relatively small compared with the number n of tasks. We present an efficient (3/2)-approximation algorithm with time complexity O(nm log(nm)) (for m > n) and O(n2 log n) (for m ≤ n). To the best of our knowledge, the best relevant known results are: (a) a (3/2 + e)-approximation algorithm with time complexity O(nm log(n/e)), (b) a fully polynomial-time approximation scheme for the case of m ≥ 16n/e, and (c) a polynomial-time approximation scheme with time complexity O(ng(1/e)) when m is bounded by a polynomial in n, where g(·) is a super-exponential function. On the other hand, the novel general technique developed in this paper for removing the e-term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems