A tight lower bound for the online bounded space hypercube bin packing problem

07/29/2021

∙

by   Yoshiharu Kohayakawa, et al.

∙

0

∙

share

In the d-dimensional hypercube bin packing problem, a given list of d-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio ρ of the online bounded space variant is Ω(log d) and O(d/log d), and conjectured that it is Θ(log d). We show that ρ is in fact Θ(d/log d), using probabilistic arguments.