论文标题
一个双重标准的fptas，用于与有限树宽度的图表上的内存约束
A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graph with Bounded Tree-width
论文作者
论文摘要
在本文中，我们研究了由HPC体系结构执行数值模拟引起的调度问题。对于恒定数量的并行机器，目标是在机器的内存约束下最小化MakePan。这些约束来自邻里图G的工作。由以前的图形G上的结果进行有界路径宽度的动机，我们的重点是邻里图G具有界限树宽度的情况。我们的结果是基于动态编程算法的双重多项式时间近似算法。它允许在最佳makepan的1 + epsilon内找到一个解决方案，在其中，机器的存储容量最多可以超过1 + epsilon的因子。该结果依赖于以特定方式使用G及其遍历的精美树分解，这可能本身很有用。不相关的机器的情况也可以进行较小的修改。
In this paper we study a scheduling problem arising from executing numerical simulations on HPC architectures. With a constant number of parallel machines, the objective is to minimize the makespan under memory constraints for the machines. Those constraints come from a neighborhood graph G for the jobs. Motivated by a previous result on graphs G with bounded path-width, our focus is on the case when the neighborhood graph G has bounded tree-width. Our result is a bi-criteria fully polynomial time approximation algorithm based on a dynamic programming algorithm. It allows to find a solution within a factor of 1 + epsilon of the optimal makespan, where the memory capacity of the machines may be exceeded by a factor at most 1 + epsilon. This result relies on the use of a nice tree decomposition of G and its traversal in a specific way which may be useful on its own. The case of unrelated machines is also tractable with minor modifications.
