master's thesis
Gordana Vujović (Author), Andrej Brodnik (Mentor), Bengt J. Nilsson (Co-mentor)

Abstract

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.

Keywords

bin packing;vector packing;online computation;competitive analysis;advice complexity;computer science;master's thesis;

Data

Language: English
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [G. Vujović]
UDC: 004(043.2)
COBISS: 91329539 Link will open in a new window
Views: 176
Downloads: 27
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Sprotno pakiranje vektorjev z nasvetom
Secondary 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.
Secondary keywords: polnjenje košev;vektorsko pakiranje;sprotno računanje;konkurenčna analiza;kompleksnost nasvetov;magisteriji;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS): Master's thesis/paper
Study programme: 1000471
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: VII, 52 str.
ID: 14092821