Analysis and Comparison of Exact and Approximate Bin Packing Algorithms (CROSBI ID 677232)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Tadic, Luka ; Afric, Petar ; Sikic, Lucija ; Kurdija, Adrian Satja ; Klemo, Vladimir ; Delac, Goran ; Silic, Marin
engleski
Analysis and Comparison of Exact and Approximate Bin Packing Algorithms
In this paper we describe the Bin packing problem (BPP) and evaluate standard state of the art approaches to its solution. Because BPP is NP- hard, there is no exact algorithm which solves the problem in polynomial time. We describe several approximate algorithms and the exact Martello- Toth-Procedure (MTP) for solving BPP. Approximate algorithms are executed in polynomial time, but they do not give optimal solutions in general. MTP searches the solution space with the help of lower bounds and approximate algorithms to minimize the solution space. For approximate algorithms we use the worst-caseto-optimal-solution ratio as a measure of effectiveness. We evaluate the relative deviation from optimal solutions for all described approximate algorithms using instances of BPP for which proven optimal solutions are found. We compare the MTP algorithm performance to those results in order to demonstrate its superiority.
Bin packing problem, discrete optimization, Martello-Toth-Procedure
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
1059-1064.
2019.
objavljeno
Podaci o matičnoj publikaciji
Proceedings of the International Conference on Computers in Technical Systems MIPRO 2019 Opatija
Podaci o skupu
MIPRO 2019
predavanje
20.05.2019-24.05.2019
Opatija, Hrvatska