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

DOI10.46298/DMTCS.8325MaRDI QIDQ5024670zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiharu Kohayakawa, Flávio K. Miyazawa, Yoshiko Wakabayashi

Publication date 27 January 2022

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.14161, https://dmtcs.episciences.org/8462

zbMATH Keywords

asymptotic performance ratiohypercube packingonline bin packingonline bounded space packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $ho$ of the online bounded space variant is $Omega(logd)$ and $O(d/logd)$, and conjectured that it is $Theta(logd)$. We show that $ho$ is in fact $Theta(d/logd)$, using probabilistic arguments.

Recommendations

• A tight lower bound for an online hypercube packing problem and bounds for prices of anarchy of a related game
• 2-space bounded online cube and hypercube packing
• Online algorithms for 1-space bounded cube packing and 2-space bounded hypercube packing
• Bounds for online bounded space hypercube packing
• Online algorithms for 1-space bounded multidimensional bin packing and hypercube packing

Cites work

• A simple on-line bin-packing algorithm
• A tight lower bound for an online hypercube packing problem and bounds for prices of anarchy of a related game
• An improved lower bound for on-line bin packing algorithms
• An on-line algorithm for multidimensional bin packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• Beating the harmonic lower bound for online bin packing
• Bounds for online bounded space hypercube packing
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• New Algorithms for Bin Packing
• New lower bounds for certain classes of bin packing algorithms
• On the online bin packing problem
• Optimal Online Algorithms for Multidimensional Packing Problems

Cited in

(4)

• A tight lower bound for an online hypercube packing problem and bounds for prices of anarchy of a related game
• Bounds for online bounded space hypercube packing
• A new upper bound 2.5545 on 2D Online Bin Packing
• A 4-space bounded approximation algorithm for online bin packing problem

This page was built for publication: A tight lower bound for the online bounded space hypercube bin packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5024670)