An improved approximation algorithm for scheduling monotonic moldable tasks
针对同构处理器上最小化完工时间的单调可塑任务调度问题，在处理器数量固定或相对任务数较小时，提出了一个(3/2)-近似算法，时间复杂度为O(nmlog(nm))或O(n^2 log n)，优于已知的(3/2+ε)-近似算法。
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(n2logn) (for m≤n). To the best of our knowledge, the best relevant known results are: (a) a (3/2+ϵ)-approximation algorithm with time complexity O(nmlog(n/ϵ)), (b) a fully polynomial-time approximation scheme for the case of m≥16n/ϵ, and (c) a polynomial-time approximation scheme with time complexity O(ng(1/ϵ)) 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 ϵ-term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems.