Naslov
Analysis and Comparison of Exact and Approximate Bin Packing Algorithms

Autori
Tadic, Luka ; Afric, Petar ; Sikic, Lucija ; Kurdija, Adrian Satja ; Klemo, Vladimir ; Delac, Goran ; Silic, Marin

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the International Conference on Computers in Technical Systems MIPRO 2019 Opatija / - , 2019, 1059-1064

Skup
42nd International ICT Convention MIPRO 2019

Mjesto i datum
Opatija, Hrvatska, 20.05.2019. - 24.05.2019

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Bin packing problem, discrete optimization, Martello-Toth-Procedure

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA