Approximate Solutions to Bin Packing Problems

Edward G. Coffman, Jr., János Csirik, and Gerhard J. Woeginger

ABSTRACT

Bin packing problems are useful models in a large variety of practical applications. We survey a quarter century of research on these problems, focusing on mathematical analysis of approximation algorithms. We cover well-known greedy algorithms for the classical one dimensional problem and specialize to on-line and bounded-space variants. We consider approximation schemes, the problem with variable bin sizes, and extensions to higher dimensions, including vector packing, two-dimensional bin packing and strip packing.