Discrete Mathematics and Combinatorics Commons^™

A Survey Of Classical And Recent Results In Bin Packing Problem, Yoga Jaideep Darapuneni

UNLV Theses, Dissertations, Professional Papers, and Capstones

In the classical bin packing problem one receives a sequence of n items 1, 2,..., n with sizes s1, s2, . . . ,sn where each item has a fixed size in (0, 1]. One needs to find a partition of the items into sets of size1, called bins, so that the number of sets in the partition is minimized and the sum of the sizes of the pieces assigned to any bin does not exceed its capacity. This combinatorial optimization problem which is NP hard has many variants as well as online and offline versions of the problem. Though …