A tight lower bound for the online bounded space hypercube bin packing problem
| Autor: | Kohayakawa, Yoshiharu, Miyazawa, Flávio Keidi, Wakabayashi, Yoshiko |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, vol. 23, no. 3, Discrete Algorithms (September 14, 2021) dmtcs:8325 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.46298/dmtcs.8325 |
| Popis: | 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 $\rho$ of the online bounded space variant is $\Omega(\log d)$ and $O(d/\log d)$, and conjectured that it is $\Theta(\log d)$. We show that $\rho$ is in fact $\Theta(d/\log d)$, using probabilistic arguments. Comment: This manuscript is derived from arXiv:1712.06763, where further material is presented and the proofs are formulated a little differently |
| Databáze: | arXiv |
| Externí odkaz: |
|