期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of 3+85828 for the deterministic
version, and 331ln21554311 for its randomized variant,
improving the previous competitive ratios of 8 and 2e5436.
We also prove lower bounds of 2.4380 on the competitive ratio of
deterministic algorithms and 1.8372 on the competitive ratio of
randomized algorithms for this problem.
关键词：Competitive Ratio, Load Balancing, lower bounds, On-Line Complexity, Related Machines
