All-Norm Approximation for Scheduling on Identical Machines
All-Norm Approximation for Scheduling on Identical Machines
复制标题
相同机器上调度的全范数近似
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Shai Taub
中科院分区：
文献类型：
--
作者：
Y. Azar;Shai Taub
我们考虑将工作分配给m台相同的机器的问题。一台机器的负载是分配给它的工作权重的总和。目标是最小化结果负载向量的范数。众所周知，对于任何固定的规范，都存在一个PTAS。另一方面，我们也知道不存在对所有规范都是最优的单一赋值。我们证明了存在一个分配，它同时保证了所有规范的最优分配的1.388近似值。这改进了Chandra和Wong在1975年给出的1.5近似值。
We consider the problem of assigning jobs to m identical machines. The load of a machine is the sum of the weights of jobs assigned to it. The goal is to minimize the norm of the resulting load vector. It is known that for any fixed norm there is a PTAS. On the other hand, it is also known that there is no single assignment which is optimal for all norms. We show that there exists one assignment which simultaneously guarantees a 1.388-approximation of the optimal assignments for all norms. This improves the 1.5 approximation given by Chandra and Wong in 1975.