Gu, Xiaodong; Chen, Guoliang; Gu, Jun; Huang, Liusheng; Jung, Yunjae Performance analysis and improvement for some linear on-line bin-packing algorithms. (English) Zbl 1046.90074 J. Comb. Optim. 6, No. 4, 455-471 (2002). Summary: 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 \(H_K\), \(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 \(H_K\) under \((0,d]\) \((d\leq 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. Cited in 1 Document MSC: 90C27 Combinatorial optimization 90C59 Approximation methods and heuristics in mathematical programming 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) Keywords:bin packing problem; approximation algorithms; worst-case performance ratio; average-case performance ratio; NPC problem PDFBibTeX XMLCite \textit{X. Gu} et al., J. Comb. Optim. 6, No. 4, 455--471 (2002; Zbl 1046.90074) Full Text: DOI