Online Two-Dimensional Vector Packing with Advice

Abstract

We consider the online two-dimensional vector packing problem, showing a lower bound of $11/5$ on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide strategies with competitive ratio $\max \left\{2,6/(1+3\tan (\pi /4-\gamma /2))+\epsilon \right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[\pi /4-\gamma /2,\pi /4+\gamma /2]$, for $0\le \gamma <\pi /3$ and $\max \left\{5/2,4/(1+2\tan (\pi /4-\gamma /2))+\epsilon \right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[\pi /4-\gamma /2,\pi /4+\gamma /2]$, for $0\le \gamma \le \pi /3$. In addition, we give a $5/2$-competitive strategy also using logarithmic advice for the unrestricted vectors case. These results should be contrasted to the currently best competitive strategy, FirstFit, having competitive ratio~$27/10$.

15 pages, 4 figures. This an extended version of an article published in "Algorithms and Complexity. CIAC 2021." Lecture Notes in Computer Science, vol 12701. Springer, https://doi.org/10.1007