A tight lower bound for an online hypercube packing problem and bounds for prices of anarchy of a related game

摘要

We prove a tight lower bound on the asymptotic performance ratio $\rho$ ofthe bounded space online $d$-hypercube bin packing problem, solving an openquestion raised in 2005. In the classic $d$-hypercube bin packing problem, weare given a sequence of $d$-dimensional hypercubes and we have an unlimitednumber of bins, each of which is a $d$-dimensional unit hypercube. The goal isto pack (orthogonally) the given hypercubes into the minimum possible number ofbins, in such a way that no two hypercubes in the same bin overlap. The boundedspace online $d$-hypercube bin packing problem is a variant of the$d$-hypercube bin packing problem, in which the hypercubes arrive online andeach one must be packed in an open bin without the knowledge of the nexthypercubes. Moreover, at each moment, only a constant number of open bins areallowed (whenever a new bin is used, it is considered open, and it remains sountil it is considered closed, in which case, it is not allowed to accept newhypercubes). Epstein and van Stee [SIAM J. Comput. 35 (2005), no. 2, 431-448]showed that $\rho$ is $\Omega(\log d)$ and $O(d/\log d)$, and conjectured thatit is $\Theta(\log d)$. We show that $\rho$ is in fact $\Theta(d/\log d)$. Toobtain this result, we elaborate on some ideas presented by those authors, andgo one step further showing how to obtain better (offline) packings of certainspecial instances for which one knows how many bins any bounded space algorithmhas to use. Our main contribution establishes the existence of such packings,for large enough $d$, using probabilistic arguments. Such packings also lead tolower bounds for the prices of anarchy of the selfish $d$-hypercube bin packinggame. We present a lower bound of $\Omega(d/\log d)$ for the pure price ofanarchy of this game, and we also give a lower bound of $\Omega(\log d)$ forits strong price of anarchy.