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

Language

English


Share

COinS