| Deep Performance Analysis of Refined Harmonic Bin Packing Alogrithm |
| |
| 摘 要： |
|
| 关 键 词： | 加密微波二进制压缩算法 NPC问题 性能分析 |
Deep performance analysis of Refined Harmonic bin packing algorithm |
| |
| Authors: | Xiaodong Gu Guoliang Chen Yinlong Xu |
| |
| Affiliation: | 1. National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, 230027, Hefei, P.R. China
|
| |
| Abstract: | Refined Harmonic (RH) is one of the best on-line bin packing algorithms. The algorithm was first proposed by Lee&;Lee in 1985 and the upper bound of the worst-case performance ratio has been proved to be 1.63596 … In this paper, it is proved that 1.63596… is also the lower bound. The average performance of RH is also studied for the first time. It is shown that the average-case performance ratio of RH is 1.28243…under the uniform distribution. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
