Award Date


Degree Type


Degree Name

Master of Science in Computer Science


Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy K. Datta

Third Committee Member

Ju-Yeon Jo

Fourth Committee Member

Zhiyong Wang

Number of Pages



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 the problem is well studied and numerous results are known, there are many open problems. Recently bin packing has gained renewed attention in as a tool in the area of cloud computing. We give a survey of different variants of the problem like 2D bin packing, strip packing, bin packing with rejection and emphasis on recent results. The thesis contains a discussion of a newly claimed tight result for First Fit Decreasing by Dosa as well as various new versions of the problem by Epstein and others.


Cloud computing; Combinatorial optimization; Combinatorial packing and covering; Data structures (Computer science)


Computer Sciences | Discrete Mathematics and Combinatorics | Mathematics

File Format


Degree Grantor

University of Nevada, Las Vegas




IN COPYRIGHT. For more information about this rights statement, please visit