University of Leicester
Browse
1607.01229v1.pdf (256.54 kB)

Improved Lower Bounds for Online Hypercube Packing

Download (256.54 kB)
journal contribution
posted on 2017-02-24, 15:00 authored by Sandy Heydrich, Rob van Stee
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.

History

Citation

arXiv:1607.01229 [cs.DS]

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Version

  • AO (Author's Original)

Published in

arXiv:1607.01229 [cs.DS]

Copyright date

2016

Available date

2017-02-24

Publisher version

https://arxiv.org/abs/1607.01229

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC