20.500.12556/RUL-133757 Online vector packing with advice Sprotno pakiranje vektorjev z nasvetom In the online setting of bin packing, items are revealed one by one, and the placement decision has to be made before the next item arrives. We focus our research towards online algorithms with advice where knowledge of future requests is used to improve the competitive ratio. We study a two-dimensional vector packing problem, a generalization of the well-known bin-packing problem, which is NP-hard. The problem is to find the minimum number of two-dimensional bins to pack a sequence of two-dimensional vectors without exceeding the bin capacity in any dimension of any bin. We show a lower bound of $(5D+12)/10$ on the competitive ratio of any {\sc AnyFit} strategy for the $D$-dimensional vector packing problem, that implies $11/5$, when $D=2$. We also show upper bounds spanning between 2 and $5/2$ depending on the angle restrictions placed on the vectors given logarithmic advice, where the currently best competitive strategy has a competitive ratio~$27/10$, albeit without using advice. V sprotnem načinu se elementi razkrivajo eden za drugim in odločitev o akciji je potrebno sprejeti preden pride naslednji element. Raziskave usmerjamo v sprotne algoritme z nasveti, v katerih se omejeno vedenje o prihodnjih zahtevah uporablja za izboljšanje konkurenčnega razmerja. Preučujemo dvodimenzionalni problem pakiranja vektorjev, posplošitev znanega problema pakiranja košev, ki je NP-težak. Izziv je najti najmanjše število dvodimenzionalnih košev, v katere je mogoče zapakirati zaporedje dvodimenzionalnih vektorjev, ne da bi presegli kapaciteto katerega koli koša v kateri koli dimenziji. Prikazujemo spodnjo mejo~$(5D+12)/10$ za konkurenčno razmerje katere koli strategije pakiranja vektorjev \textsc{AnyFit} za D-dimenzionalni problem, kar pomeni~$11/5$ za $D=2$. Prikazujemo tudi zgornje meje med $2$ in $5/2$, odvisno od omejitev kota vektorjev ob logaritemsko velikem nasvetu. Trenutno najboljša konkurenčna strategija ima konkurenčno razmerje $27/10$, brez uporabe nasvetov. Bin Packing Vector Packing Online Computation Competitive Analysis Advice Complexity polnjenje košov vektorsko pakiranje sprotno računanje konkurenčna analiza kompleksnost nasvetov. true false false Angleški jezik Slovenski jezik Magistrsko delo/naloga 2021-12-14 12:45:02 2021-12-14 12:45:08 2022-09-13 03:52:32 0000-00-00 00:00:00 2021 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 29485 91329539 Vujovic_Gordana_-_Sprotno_pakiranje_vektorjev_z_nasvetom.pdf Vujovic_Gordana_-_Sprotno_pakiranje_vektorjev_z_nasvetom.pdf 1 54C5DE0E870D361B32DF5E094CD30838 306cf19f1bd9b14e79f3cd15920444b4fc42cff0bf650c584d2bd3ebada66812 2baa8d5f-5cd3-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=152097 Fakulteta za računalništvo in informatiko 0 0 0