de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Improved Lower Bounds for Online Hypercube Packing

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons79285

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

Locator
There are no locators available
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.