Τομέας Θεωρητικής Πληροφορικής

Library of the School of Science

Library of the School of Science

2016-07-08

2016

Δαβιλάς Κωνσταντίνος

Βασίλειος Ζησιμόπουλος

Αναλυση bin packing problem

Greek

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.

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.

ΝP-Hardness, Bin Packing, Exact Algorithms, Approximation Algorithms, MapReduce

Yes

6-7

No

24

42