Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Efficient 1-Space Bounded Hypercube Packing Algorithm

Published: 01 November 2020 Publication History

Abstract

A space bounded O(d/logd)-competitive hypercube packing algorithm with one active bin only is presented. As a starting point we give a simple 1-space bounded hypercube packing algorithm with competitive ratio (3/2)d+O((21/16)d), for d3.

References

[1]
Balogh, J., Békesi, J., Dósa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: 26th Annual European Symposium on Algorithms (ESA 2018). Article No. 5; pp. 5:1–5:14
[2]
Balogh, J., Békesi, J., Dósa, G., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. arXiv:1807.0554v1
[3]
Brown, D.J.: A lower bound for on-line one-dimensional bin packing algorithms. Technical Report R-864, Coordinated Sci. Lab, Urbana, Illinois (1979)
[4]
Christensen HI, Khan A, Pokutta S, and Tetali PApproximation and online algorithms for multidimensional bin packing: a surveyComput. Sci. Rev.20172463-7936557681398.68007
[5]
Coppersmith D and Raghavan PMultidimensional on-line bin packing: algorithms and worst-case analysisOper. Res. Lett.19898117-209835680676.90050
[6]
Csirik J, Frenk J, and Labbé MTwo-dimensional rectangle packing: on-line methods and resultsDiscrete Appl. Math.1993453197-20412367250786.90055
[7]
Csirik J and Johnson DSBounded space on-line bin packing: best is better than firstAlgorithmica2001312115-13818456940980.68141
[8]
Epstein L and van Stee ROptimal online algorithms for multidimensional packing problemsSIAM J. Comput.2005352431-44821914511092.68047
[9]
Grzegorek P and Januszewski J Online algorithms for 3-space bounded 2-dimensional bin packing and square packing Rom. J. Inf. Sci. Technol. 2014 17 2 190-203
[10]
Grzegorek P and Januszewski JA note on one-space bounded square packingInf. Process. Lett.201511511872-87633690241331.68298
[11]
Grzegorek P and Januszewski JDrawer algorithms for 1-space bounded multidimensional hyperbox packingJ. Comb. Optim.2019371011-104439284231425.90094
[12]
Han X, Chin FYL, Ting HF, Zhang G, and Zhang YA new upper bound on 2D online bin packingACM Trans. Algorithms20117450:1-50:1828369891295.68133
[13]
Han X, Fujita S, and Guo H A two-dimensional harmonic algorithm with performance ratio 2.7834 IPSJ SIG Not. 2001 93 43-50
[14]
Heydrich, S., van Stee, R.: Beating the harmonic lower bound for online bin packing. In: 43rd International Colloquium on Automata, Languages, and Programming, LIPIcs—Leibniz International Proceedings in Informatics, vol. 55, pp. 41:1–41:14. Schloss Dagstuhl - LZI, Wadern (2016)
[15]
Januszewski J and Lassak MOn-line packing sequences of cubes in the unit cubeGeom. Dedic.1997673285-29314758730891.52009
[16]
Januszewski J and Zielonka ŁImproved online algorithms for 2-space bounded 2-dimensional bin packingInt. J. Found. Comput. Sci.2016274407-4293519659
[17]
Januszewski J and Zielonka ŁEfficient online packing of 4-dimensional cubes into the unit cubeStud. Sci. Math. Hung.2018553305-32638655871413.68179
[18]
Januszewski J and Zielonka ŁOnline packing of d-dimensional boxes into the unit cubePeriod. Math. Hung.2020412914407251426
[19]
Johnson DSFast algorithms for bin packingJ. Comput. Syst. Sci.197483272-3143733700284.68023
[20]
Johnson DS, Demers A, Ullman JD, Garey MR, and Graham RLWorst-case performance bounds for simple one-dimensional packing algorithmsSIAM J. Comput.197434299-3254343960297.68028
[21]
Lee CC and Lee DTA simple on-line bin-packing algorithmJ. ACM1985323562-5727962010629.68045
[22]
Liang FMA lower bound for on-line bin packingInf. Process. Lett.198010276-795645030444.68061
[23]
Ramanan P, Brown DJ, Lee C, and Lee DOn-line bin packing in linear timeJ. Algorithms1989103305-32610069880682.68057
[24]
Seiden SSOn the online bin packing problemJ. ACM2002495640-67121470951326.68337
[25]
Seiden SS and van Stee RNew bounds for multidimensional packingAlgorithmica2003363261-29319842221045.68160
[26]
Sloane, N.J.A.: Gould’s sequence. https://oeis.org/A001316
[27]
Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University. Department of Electrical Engineering. Computer Sciences Laboratory (1971)
[28]
van Vliet AAn improved lower bound for on-line bin packing algorithmsInf. Process. Lett.1992435277-28411933730764.68083
[29]
Woeginger GImproved space for bounded-space, on-line bin-packingSIAM J. Discrete Math.199364575-58112413970806.90068
[30]
Yao ACCNew algorithms for bin packingJ. ACM1980272207-2275670420434.68053
[31]
Zhang Y, Chin FYL, Ting HF, and Han XOnline algorithms for 1-space bounded multi dimensional bin packing and hypercube packingJ. Comb. Optim.2013262223-23630718681275.90086
[32]
Zhang Y, Chin FYL, Ting HF, Han X, Poon CK, Tsin YH, and Ye DOnline algorithms for 1-space bounded 2-dimensional bin packing and square packingTheor. Comput. Sci.2014554135-14932628831360.68911

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica
Algorithmica  Volume 82, Issue 11
Nov 2020
289 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2020
Accepted: 02 May 2020
Received: 24 May 2017

Author Tags

  1. Bin packing
  2. Online algorithm
  3. Asymptotic competitive ratio
  4. Cube
  5. Hypercube
  6. One-space bounded

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media