Online vector packing with advice

Vujović, Gordana (author), Brodnik, Andrej (mentor), Nilsson, Bengt J. (comentor)

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.

• Language: English
• Keywords: Bin Packing, Vector Packing, Online Computation, Competitive Analysis, Advice Complexity
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-133757
• COBISS.SI-ID: 91329539
• Publication date in RUL: 14.12.2021

VUJOVIĆ, Gordana, 2021, Online vector packing with advice [online]. Master’s thesis. [Accessed 23 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=133757

Secondary language

• Language: Slovenian
• Title: Sprotno pakiranje vektorjev z nasvetom

Abstract

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.

• Keywords: polnjenje košov, vektorsko pakiranje, sprotno računanje, konkurenčna analiza, kompleksnost nasvetov.