文章基本信息

标题：On-Line Load Balancing for Related Machines
本地全文：下载
作者：Piotr Berman ; Moses Charikar ; Marek Karpinski 等
期刊名称：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