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(nmlog(nm)) (for m > n) and O(n(2) log n) (for m <= n). To the best of our knowledge, the best relevant known results are: (a) a (3/2 + epsilon)-approximation algorithm with time complexity O(nm log(n/epsilon)), (b) a fully polynomial-time approximation scheme for the case of m >= 16n/epsilon, and (c) a polynomial-time approximation scheme with time complexity O(n(g(1/epsilon))) when m is bounded by a polynomial in n , where g(center dot) is a super-exponential function. On the other hand, the novel general technique developed in this paper for removing the epsilon-term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)

Automated summary

We propose an efficient (3/2)-approximation algorithm for scheduling monotonic moldable tasks on identical processors. The algorithm has a time complexity of O(nmlog(nm)) (for m > n) and O(n(2) log n) (for m <= n). The best known results include a (3/2 + epsilon)-approximation algorithm with a time complexity of O(nm log(n/epsilon)), a fully polynomial-time approximation scheme for m >= 16n/epsilon, and a polynomial-time approximation scheme with a time complexity of O(n(g(1/epsilon))) for bounded m. Additionally, the paper introduces a novel general technique for improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems.