English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Improved Lower Bounds for Online Hypercube Packing

MPS-Authors
/persons/resource/persons79285

Heydrich,  Sandy
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:1607.01229.pdf
(Preprint), 257KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Heydrich, S., & van Stee, R. (2016). Improved Lower Bounds for Online Hypercube Packing. Retrieved from http://arxiv.org/abs/1607.01229.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-54AF-0
Abstract
Packing a given sequence of items into as few bins as possible in an online fashion is a widely studied problem. We improve lower bounds for packing hypercubes into bins in two or more dimensions, once for general algorithms (in two dimensions) and once for an important subclass, so-called Harmonic-type algorithms (in two or more dimensions). Lastly, we show that two adaptions of the ideas from the best known one-dimensional packing algorithm to square packing also do not help to break the barrier of 2.