master's thesis
Povzetek
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.
Ključne besede
bin packing;vector packing;online computation;competitive analysis;advice complexity;computer science;master's thesis;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2021 |
Tipologija: |
2.09 - Magistrsko delo |
Organizacija: |
UL FRI - Fakulteta za računalništvo in informatiko |
Založnik: |
[G. Vujović] |
UDK: |
004(043.2) |
COBISS: |
91329539
|
Št. ogledov: |
176 |
Št. prenosov: |
27 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Slovenski jezik |
Sekundarni naslov: |
Sprotno pakiranje vektorjev z nasvetom |
Sekundarni povzetek: |
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. |
Sekundarne ključne besede: |
polnjenje košev;vektorsko pakiranje;sprotno računanje;konkurenčna analiza;kompleksnost nasvetov;magisteriji;Računalništvo;Univerzitetna in visokošolska dela; |
Vrsta dela (COBISS): |
Magistrsko delo/naloga |
Študijski program: |
1000471 |
Komentar na gradivo: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Strani: |
VII, 52 str. |
ID: |
14092821 |