Αναλυση bin packing problem

Graduate Thesis uoadl:1324039 1778 Read counter

Unit:
Τομέας Θεωρητικής Πληροφορικής
Library of the School of Science
Deposit date:
2016-07-08
Year:
2016
Author:
Δαβιλάς Κωνσταντίνος
Supervisors info:
Βασίλειος Ζησιμόπουλος
Original Title:
Αναλυση bin packing problem
Languages:
Greek
Summary:
The purpose of this thesis is to study the NP-complete Bin Packing Problem.
Given a
set of numbers / weights and a set of bins (bins) of given capacity, the
minimum number
of bins required is to be found, in order the bins to contain all the weights /
numbers and
no bin exceeds its capacity. We will see the main practical applications of Bin
Packing
Problem. We will report and study the most important algorithms used for the
solution of
the problem and their most substantial applications. Furthermore we will study
the
problem of Bin Packing Problem in correspondence with the MapReduce as it can
offer
solutions to the Bin Packing Problem in cliques. Finally, we will examine the
problem in
a path where each element Xi must be in the same bucket with Xi+1, proposing
some
algorithms that could resolve the problem by analyzing their pluses and
minuses.
Keywords:
ΝP-Hardness, Bin Packing, Exact Algorithms, Approximation Algorithms, MapReduce
Index:
Yes
Number of index pages:
6-7
Contains images:
No
Number of references:
24
Number of pages:
42
document.pdf (626 KB) Open in new window