Improved Bounds for the Online Scheduling Problem
Improved Bounds for the Online Scheduling Problem
复制标题
DOI：
10.1137/s0097539702403438
复制
发表时间：
2003-03
期刊：
影响因子：
--
通讯作者：
Johan Rudin;R. Chandrasekaran
中科院分区：
文献类型：
--
作者：
Johan Rudin;R. Chandrasekaran
这里考虑的问题与[G. Galambos和G. J. Woeginger，编，SIAM J. COMPUT.，22（1993），pp. 349- 355]。这是一个以最大完工时间为目标，以竞争比最小为目标的多机在线排序问题。在本文中，我们表明，$\sqrt{3}$是一个下界，这个竞争比m=4。特别是，我们展示了如何强制对任何正的$\sqrt{3\，}-\sqrt $的下界。这减小了已知算法的性能之间的差距[S.阿尔伯斯，在第29届年度ACM计算理论研讨会论文集，ACM，纽约，1997年，pp. 130--139]和下限。所使用的方法介绍了一种方法来建立任务主的策略。
The problem considered here is the same as the one discussed in [G. Galambos and G. J. Woeginger, eds., SIAM J. Comput., 22 (1993), pp. 349--355]. It is an m-machine online scheduling problem in which we wish to minimize the competitive ratio for the makespan objective. In this paper, we show that $\sqrt{3}$ is a lower bound on this competitive ratio for m=4. In particular, we show how to force a lower bound of $\sqrt{3\,}-\epsilon $ for any positive $\epsilon $. This reduces the gap between the performance of known algorithms [S. Albers, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 130--139] and the lower bound. The method used introduces an approach to building the task master's strategy.