Problem polnjenja košev v povezavi z omejitvijo kardinalnosti

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Remic]
UDK:	004(043.2)
COBISS:	8451156
Št. ogledov:	45
Št. prenosov:	3
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Cardinality constrained bin packing
Sekundarni povzetek:	Bin packing is an optimizational NP-hard problem of packing items of given sizes into minimum number of capacity-limited bins. Besides the basic problem, numerous other variants of bin packing exist. The cardinality constrained bin packing adds an additional constraint that the number of items in a bin must not exceed a given limit Nmax. Some well-known algorithms for solving the general bin packing problem are described, along with three specific algorithms for solving the cardinality constrained bin packing problem. The FFD, RFF and Zhang's algorithms are compared to the three specific algorithms on random lists of items with 0%, 10%, 30% and 50% of large items. The behaviour of all algorithms when Nmax increases is also studied. Results show that all three specific algorithms outperform the general algorithms on lists with low percentage of large items. One of the specific algorithms performs better or equally even on lists with high percentage of large items and is therefore of significant interest. The behaviour when Nmax increases shows that all three specific algorithms can be used for solving the general bin packing problem as well.
Sekundarne ključne besede:	approximation algorithms;comparison;FFD;RFF;Zhang's algorithm;computer science;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	43 str.
ID:	23984544