Award Date

December 2016

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

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

67

Abstract

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.

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS