Online Two-Dimensional Vector Packing with Advice

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\big/\big(1+3\tan(π/4-γ/2)\big)+ε\right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[π/4-γ/2,π/4+γ/2]$, for $0\leqγ<π/3$ and $\max\left\{5/2,4\big/\big(1+2\tan(π/4-γ/2)\big)+ε\right\}$ and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range $[π/4-γ/2,π/4+γ/2]$, for $0\leqγ\leqπ/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$.

No reviews yet.

No comments yet.