Award Date

December 2016

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

laxmi gewali

Fourth Committee Member

venkatesan muthukumar

Number of Pages



The bin packing problem requires packing a set of objects into a finite number of bins of fixed capacity in a way that minimizes the number of bins used. We consider the online version of the problem where items arrive over tine and a decision has to be made as soon as an element is available. Online algorithms can be analyzed in terms of competitiveness, a measure of performance that compares the solution obtained online with the optimal offline solution for the same problem, where the lowest possible competitiveness is best. Online processing is difficult due to the fact that unpredictable item sizes may appear. A number of online algorithms such First-Fit, Next-Fit, Best-Fit, Worst Fit and Harmonic have been proposed and studied in the literature. In this thesis we examine how well these algorithms perform in practice. Our results that practical performance is differs substantially from the worst case online measure.


Computer Sciences

File Format


Degree Grantor

University of Nevada, Las Vegas




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