| 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 等数据库收录！ |
|
