The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case (Q1429289)

The problem: \(n\) item-rectangles, each with a given width \(w_j\) and a given height \(h_j\), \(1 \leq j \leq n\), need to be packed in as few bin-rectangles (each having width \(W\) and height \(H\)) as possible such that no pair of item-rectangles overlap, and such that the item-rectangles are placed axis-parallel, with fixed orientation. The results: after having reviewed the known lower bounds due to \textit{S. Martello} and \textit{D. Vigo} [Manage. Sci. 44, No.3, 388-399 (1998; Zbl 0989.90114)], and \textit{S. Fekete} and \textit{J. Schepers} [On more-dimensional packing II: Bounds. (English). Report 97.289, Universität zu Köln. (2000)], four new lower bounds are proposed. The relation between these bounds and previous bounds is investigated, as well as the algorithmic complexity of computing these new lower bounds.