Bounded space on-line bin packing: Best is better than first

We present a sequence of new linear-time, bounded-space, on-line bin packin g algorithms, the K-Bounded Best Fit algorithms (BBFK). They are based on t he Theta (n log n) Best Fit algorithm in much the same way as the Next-K Fi t algorithms are based on the Theta (n log n) First Fit algorithm. Unlike t he Next-K Fit algorithms, whose asymptotic worst-case ratios approach the l imiting value of 17 from above as K --> infinity but never reach it, these new algorithms have worst-case ratio 17/10 for all K greater than or equal to 2. They also have substantially better average performance than their bo unded-space competition, as we have determined based on extensive experimen tal results summarized here for instances with item sizes drawn independent ly and uniformly from intervals of the form (0, u], 0 < u <less than or equ al to> 1. Indeed, for each u < 1, it appears that there exists a fixed memo ry bound K(u) such that BBFK(u) obtains significantly better packings on av erage than does the First Fit algorithm, even though the latter requires un bounded storage and has a significantly greater running time. For u = 1, BB FK can still outperform First Fit (and essentially equal Best Fit) if K is allowed to grow slowly. We provide both theoretical and experimental result s concerning the growth rates required.