An Execution Rate Of 2.7687 Two-dimensional Harmonic Algorithm

In this paper, we study an on-line version of the two-dimensional bin packing problem that is the problem of packing a list of rectangular items into a minimum number of unit-square bins in an on-line manner. An on-line algorithm called RTDH (Refined Two Dimensional HARMONIC) is proposed and analyzed. We show that RTDH can achieve an asymptotic worst-case ratio of less than 2.7687, which beats the best-known bound 2.85958.