A tight lower bound for the online bounded space hypercube bin packing problem
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 $\Om...
Main Authors: | Yoshiharu Kohayakawa, Flávio Keidi Miyazawa, Yoshiko Wakabayashi |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2021-09-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/8325/pdf |
Similar Items
-
A note on limits of sequences of binary trees
by: Rudolf Grübel
Published: (2023-05-01) -
How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm
by: Juan Carlos García-Altamirano, et al.
Published: (2023-03-01) -
Foundations of Online Structure Theory II: The Operator Approach
by: Rod Downey, et al.
Published: (2021-07-01) -
Homomorphically Full Oriented Graphs
by: Thomas Bellitto, et al.
Published: (2023-10-01) -
Anti-power $j$-fixes of the Thue-Morse word
by: Marisa Gaetz
Published: (2021-02-01)