Online Two-Dimensional Vector Packing with Advice
share
We consider the online two-dimensional vector packing problem, showing a lower bound of 11/5 on the competitive ratio of any AnyFit strategy for the problem. We provide strategies with competitive ratio max{2,6/(1+3tan(π/4-γ/2))+ϵ} 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≤γ<π/3 and max{5/2,4/(1+2tan(π/4-γ/2))+ϵ} 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≤γ≤π/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.
READ FULL TEXT