Performance Analysis and Improvement for Some Linear On-Line Bin-Packing Algorithms |
| |
| Authors: | Xiaodong Gu Guoliang Chen Jun Gu Liusheng Huang Yunjae Jung |
| |
| Affiliation: | (1) National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, People's Republic of China;(2) Department of Computer Science, University of Science and Technology of Hong Kong, Hong Kong, People's Republic of China;(3) National High Performance Computing Center at Hefei, Department of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, People's Republic of China;(4) Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA |
| |
| Abstract: | The study on one-dimensional bin packing problem may bring about many important applications such as multiprocessor scheduling, resource allocating, real-world planning and packing. Harmonic algorithms (including HK, RH, etc.) for bin packing have been famous for their linear-time and on-line properties for a long time. This paper profoundly analyzes the average-case performance of harmonic algorithms for pieces of i.i.d. sizes, provides the average-case performance ratio of HK under (0,d] (d  1) uniform distribution and the average-case performance ratio of RH under (0,1] uniform distribution. We also finished the discussion of the worst-case performance ratio of RH. Moreover, we propose a new improved version of RH that obtains better worst- and average-case performance ratios. |
| |
| Keywords: | bin packing problem approximation algorithms worst-case performance ratio average-case performance ratio NPC problem |
| 本文献已被 SpringerLink 等数据库收录！ |
|
