Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 1005327

Analysis and Comparison of Exact and Approximate Bin Packing Algorithms


Tadic, Luka; Afric, Petar; Sikic, Lucija; Kurdija, Adrian Satja; Klemo, Vladimir; Delac, Goran; Silic, Marin
Analysis and Comparison of Exact and Approximate Bin Packing Algorithms // Proceedings of the International Conference on Computers in Technical Systems MIPRO 2019 Opatija
Opatija, Hrvatska, 2019. str. 1059-1064 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)


CROSBI ID: 1005327 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

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-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


Projekti:
HRZZ-IP-2018-01-6423 - Pouzdani kompozitni primjenski sustavi zasnovani na web uslugama (RELS) (Srbljić, Siniša, HRZZ - 2018-01) ( POIROT)

Ustanove:
Fakultet elektrotehnike i računarstva, Zagreb


Citiraj ovu publikaciju:

Tadic, Luka; Afric, Petar; Sikic, Lucija; Kurdija, Adrian Satja; Klemo, Vladimir; Delac, Goran; Silic, Marin
Analysis and Comparison of Exact and Approximate Bin Packing Algorithms // Proceedings of the International Conference on Computers in Technical Systems MIPRO 2019 Opatija
Opatija, Hrvatska, 2019. str. 1059-1064 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)
Tadic, L., Afric, P., Sikic, L., Kurdija, A., Klemo, V., Delac, G. & Silic, M. (2019) Analysis and Comparison of Exact and Approximate Bin Packing Algorithms. U: Proceedings of the International Conference on Computers in Technical Systems MIPRO 2019 Opatija.
@article{article, year = {2019}, pages = {1059-1064}, keywords = {Bin packing problem, discrete optimization, Martello-Toth-Procedure}, title = {Analysis and Comparison of Exact and Approximate Bin Packing Algorithms}, keyword = {Bin packing problem, discrete optimization, Martello-Toth-Procedure}, publisherplace = {Opatija, Hrvatska} }
@article{article, year = {2019}, pages = {1059-1064}, keywords = {Bin packing problem, discrete optimization, Martello-Toth-Procedure}, title = {Analysis and Comparison of Exact and Approximate Bin Packing Algorithms}, keyword = {Bin packing problem, discrete optimization, Martello-Toth-Procedure}, publisherplace = {Opatija, Hrvatska} }




Contrast
Increase Font
Decrease Font
Dyslexic Font