An improved approximation algorithm for scheduling monotonic moldable tasks
An improved approximation algorithm for scheduling monotonic moldable tasks
复制标题
一种改进的单调可塑任务调度近似算法
DOI：
10.1016/j.ejor.2022.08.034
复制
发表时间：
2022
影响因子：
6.4
通讯作者：
Bo Chen
中科院分区：
文献类型：
--
作者：
Fangfang Wu;Xiandong Zhang;Bo Chen
我们关心的是在相同的处理器上调度单调可塑任务以最小化完工时间的问题。我们关注自然情况，即作为资源的处理器数量 m 是固定的或与任务数量 n 相比相对较小。我们提出了一种高效的 (3/2) 近似算法，其时间复杂度为 O (n m log (n m))（对于 m> n）和 O (n 2 log n)（对于 m≤ n）。据我们所知，最相关的已知结果是：(a) 时间复杂度为 O (n m log (n/ϵ)) 的 (3/2+ ϵ) 逼近算法，(b) m≥ 16 n/ϵ 情况下的完全多项式时间逼近方案，以及 (c) 当 m 受多项式约束时，时间复杂度为 O (n g (1/ϵ)) 的多项式时间逼近方案n，其中g(·)是超指数函数。另一方面，本文开发的用于去除最坏情况性能比中的 ϵ 项的新颖通用技术可以应用于改善其他组合优化问题的某些对偶算法的性能保证。
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 (n m log (n m))(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+ ϵ)-approximation algorithm with time complexity O (n m log (n/ϵ)),(b) a fully polynomial-time approximation scheme for the case of m≥ 16 n/ϵ, and (c) a polynomial-time approximation scheme with time complexity O (n g (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.