English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

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 Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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.