ABSTRACT

We present an nΔO(k2) time algorithm to obtain an optimal solution for 1-dimensional cutting stock problem: the bin packing problem of packing n items onto unit capacity bins under the restriction that the number of item sizes k is fixed, where Δ is the reciprocal of the size of the smallest item. We employ elementary ideas in both the design and analysis our algorithm.

Keywords: Bin Packing; Cutting Stock Problems; Approximation Algorithms; Approximation Schemes; Design and Analysis of Algorithms