We present a sequence of new linear‐time, bounded‐space, on‐line bin packing algorithms, the K ‐Bounded Best Fit algorithms (BBF
K
). They are based on the θ(n log n) Best Fit algorithm in much the same way as the Next‐K Fit algorithms are based on the θ(n log n) First Fit algorithm. Unlike the Next‐K Fit algorithms, whose asymptotic worst‐case ratios approach the limiting value of \frac 17 10 from above as K \rightarrow ∈fty but never reach it, these new algorithms have worst‐case ratio \frac 17 10 for all K \geq 2 . They also have substantially better average performance than their bounded‐space competition, as we have determined based on extensive experimental results summarized here for instances with item sizes drawn independently and uniformly from intervals of the form (0, u] , 0 < u ≤ 1 . Indeed, for each u < 1 , it appears that there exists a fixed memory bound K(u) such that BBF
K(u)
obtains significantly better packings on average than does the First Fit algorithm, even though the latter requires unbounded storage and has a significantly greater running time. For u = 1 , BBF
K
can still outperform First Fit (and essentially equal Best Fit) if K is allowed to grow slowly. We provide both theoretical and experimental results concerning the growth rates required.
