A better semi-online algorithm for Q3/s1 = s2≤ s3/Cmin with the known largest size |
| |
作者单位: | [1]Department of Mathematics, Zhejiang University, Hangzhou 310027, China [2]School of Mathematics &: Information Science, Wenzhou University, Wenzhou 325035, China |
| |
基金项目: | Supported by the National Natural Science Foundation of China (No. 60674071) |
| |
摘 要: | This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 < s1 = s2 = r ≤ t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max{2, (3s+6)/(s+6) } is presented. We also show the lower bound is at least max{2, (3s)/(s+6)}. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.
|
关 键 词: | 半在线算法 最大尺寸 最大规模 统一问题 优化算法 竞争比 机器 竞争力 |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
|