In this note we present a simplified proof of a lower bound for on-line bin packing. This proof also covers the well-known result given by Liang in Inform. Process Lett. 10 (1980) 76–79.

doi.org/10.1016/0166-218X(93)90037-O, hdl.handle.net/1765/11696
Discrete Applied Mathematics
Erasmus School of Economics

Frenk, H., & Galambos, G. (1993). A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case. Discrete Applied Mathematics, 173–178. doi:10.1016/0166-218X(93)90037-O