Online vector packing with adviceVujović, Gordana (Avtor) Brodnik, Andrej (Mentor) Nilsson, Bengt J. (Komentor) Bin PackingVector PackingOnline ComputationCompetitive AnalysisAdvice ComplexityIn 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.20212021-12-14 12:45:02Magistrsko delo/naloga133757sl