An Optimal Algorithm for 1-D Cutting Stock Problem

Abstract

We present an $n{\Delta }^{O(k^2)}$ 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 $\Delta$ is the reciprocal of the size of the smallest item. We employ elementary ideas in both the design and analysis our algorithm.

7 pages

References in corpus (1)

• A Fast Scalable Heuristic for Bin Packing