Document Open Access Logo

Fully-Dynamic Bin Packing with Little Repacking

Authors Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.51.pdf
  • Filesize: 0.69 MB
  • 24 pages

Document Identifiers

Author Details

Björn Feldkord
  • Paderborn University, Paderborn, Germany
Matthias Feldotto
  • Paderborn University, Paderborn, Germany
Anupam Gupta
  • Carnegie Mellon University, Pittsburgh, USA
Guru Guruganesh
  • Carnegie Mellon University, Pittsburgh, USA
Amit Kumar
  • IIT Delhi, New Delhi, India
Sören Riechers
  • Paderborn University, Paderborn, Germany
David Wajc
  • Carnegie Mellon University, Pittsburgh, USA

Funding

  • Gupta, Anupam: Work done in part while the authors were at the Simons Institute for the Theory of Computing.
  • Guruganesh, Guru: Work done in part while the authors were at the Simons Institute for the Theory of Computing.
  • Kumar, Amit: Work done in part while the authors were at the Simons Institute for the Theory of Computing.
  • Wajc, David: Work done in part while the authors were at the Simons Institute for the Theory of Computing.

Cite As Get BibTex

Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-Dynamic Bin Packing with Little Repacking. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 51:1-51:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.51

Abstract

We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost c_i >= 0, and we want to use alpha * OPT bins and incur a movement cost gamma * c_i, either in the worst case, or in an amortized sense, for alpha, gamma as small as possible. We call gamma the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Bin Packing
  • Fully Dynamic
  • Recourse
  • Tradeoffs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A new and improved algorithm for online bin packing. arXiv preprint arXiv:1707.01728, 2017. Google Scholar
  2. János Balogh, József Békési, and Gábor Galambos. New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci., 440-441:1-13, 2012. Google Scholar
  3. János Balogh, József Békési, Gábor Galambos, and Mihály Csaba Markót. Improved lower bounds for semi-online bin packing problems. Computing, 84(1-2):139-148, 2009. URL: http://dx.doi.org/10.1007/s00607-008-0023-6.
  4. János Balogh, József Békési, Gábor Galambos, and Gerhard Reinelt. Lower bound for the online bin packing problem with restricted repacking. SIAM J. Comput., 38(1):398-410, 2008. URL: http://dx.doi.org/10.1137/050647049.
  5. János Balogh, József Békési, Gábor Galambos, and Gerhard Reinelt. On-line bin packing with restricted repacking. J. Comb. Optim., 27(1):115-131, 2014. Google Scholar
  6. Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully dynamic bin packing revisited. In APPROX-RANDOM, volume 40 of LIPIcs, pages 135-151. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  7. Edward G Coffman Jr, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of Combinatorial Optimization, pages 455-531. Springer, 2013. Google Scholar
  8. Robert M Corless, Gaston H Gonnet, D EG Hare, David J Jeffrey, and Donald E Knuth. On the Lambert-W function. Advances in Computational mathematics, 5(1):329-359, 1996. Google Scholar
  9. Leah Epstein and Asaf Levin. A robust APTAS for the classical bin packing problem. Math. Program., 119(1):33-49, 2009. URL: http://dx.doi.org/10.1007/s10107-007-0200-y.
  10. Leah Epstein and Asaf Levin. A robust APTAS for the classical bin packing problem. Math. Program., 119(1):33-49, 2009. Google Scholar
  11. Björn Feldkord, Matthias Feldotto, and Sören Riechers. A tight approximation for fully dynamic bin packing without bundling. arXiv preprint arXiv:1711.01231, 2017. Google Scholar
  12. Giorgio Gambosi, Alberto Postiglione, and Maurizio Talamo. New algorithms for on-line bin packing. In Algorithms and Complexity, Proceedings of the First Italian Conference, pages 44-59, 1990. Google Scholar
  13. Giorgio Gambosi, Alberto Postiglione, and Maurizio Talamo. Algorithms for the relaxed online bin-packing model. SIAM J. Comput., 30(5):1532-1551, 2000. URL: http://dx.doi.org/10.1137/S0097539799180408.
  14. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  15. Anupam Gupta, Guru Guruganesh, Amit Kumar, and David Wajc. Fully-dynamic bin packing with limited repacking. arXiv preprint arXiv:1711.02078, 2017. Google Scholar
  16. Sandy Heydrich and Rob van Stee. Beating the harmonic lower bound for online bin packing. In 43rd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl, 2016. Google Scholar
  17. Rebecca Hoberg and Thomas Rothvoss. A logarithmic additive integrality gap for bin packing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2616-2625. SIAM, 2017. Google Scholar
  18. Dorit S Hochbaum. Approximation algorithms for NP-hard problems. PWS Publishing Co., 1996. Google Scholar
  19. Zoran Ivković. Fully dynamic approximation algorithms. PhD thesis, University of Delaware, 1996. Google Scholar
  20. Zoran Ivković and Errol L. Lloyd. A fundamental restriction on fully dynamic maintenance of bin packing. Inf. Process. Lett., 59(4):229-232, 1996. Google Scholar
  21. Zoran Ivković and Errol L. Lloyd. Fully dynamic algorithms for bin packing: Being (mostly) myopic helps. SIAM J. Comput., 28(2):574-611, 1998. URL: http://dx.doi.org/10.1137/S0097539794276749.
  22. Zoran Ivković and Errol L. Lloyd. Fully dynamic bin packing. In Fundamental Problems in Computing, pages 407-434. Springer, 2009. Google Scholar
  23. Klaus Jansen and Kim-Manuel Klein. A robust AFPTAS for online bin packing with polynomial migration,. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 589-600. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_50.
  24. David S. Johnson. Fast allocation algorithms. In 13th Annual Symposium on Switching and Automata Theory, College Park, Maryland, USA, October 25-27, 1972, pages 144-154. IEEE Computer Society, 1972. URL: http://dx.doi.org/10.1109/SWAT.1972.4.
  25. David S. Johnson. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973. Google Scholar
  26. David S. Johnson. Fast algorithms for bin packing. J. Comput. Syst. Sci., 8(3):272-314, 1974. URL: http://dx.doi.org/10.1016/S0022-0000(74)80026-7.
  27. David S. Johnson, Alan Demers, Jeffrey D. Ullman, Michael R Garey, and Ronald L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325, 1974. Google Scholar
  28. Edward G. Coffman Jr., M. R. Garey, and David S. Johnson. Dynamic bin packing. SIAM J. Comput., 12(2):227-258, 1983. URL: http://dx.doi.org/10.1137/0212014.
  29. Chung C. Lee and Der-Tsai Lee. A simple on-line bin-packing algorithm. J. ACM, 32(3):562-572, 1985. URL: http://dx.doi.org/10.1145/3828.3833.
  30. Prakash Ramanan, Donna J Brown, Chung-Chieh Lee, and Der-Tsai Lee. On-line bin packing in linear time. Journal of Algorithms, 10(3):305-326, 1989. Google Scholar
  31. Michael B Richey. Improved bounds for harmonic-based bin packing algorithms. Discrete Applied Mathematics, 34(1-3):203-227, 1991. Google Scholar
  32. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Google Scholar
  33. Steven S. Seiden. On the online bin packing problem. J. ACM, 49(5):640-671, 2002. URL: http://dx.doi.org/10.1145/585265.585269.
  34. James J Sylvester. On a point in the theory of vulgar fractions. American Journal of Mathematics, 3(4):332-335, 1880. Google Scholar
  35. Jeffrey D. Ullman. The performance of a memory allocation algorithm. Technical report, Princeton University. Department of Electrical Engineering. Computer Science Laboratory, 1971. Google Scholar
  36. André van Vliet. Lower and Upper Bounds for On-line Bin Packing and Scheduling Heuristics: Onder-en Bovengrenzen Voor On-line Bin Packing en Scheduling Heuristieken. Thesis Publ., 1995. Google Scholar
  37. Gerhard Woeginger. Improved space for bounded-space, on-line bin-packing. SIAM Journal on Discrete Mathematics, 6(4):575-581, 1993. Google Scholar
  38. Prudence W. H. Wong, Fencol C. C. Yung, and Mihai Burcea. An 8/3 lower bound for online dynamic bin packing. In ISAAC, volume 7676 of Lecture Notes in Computer Science, pages 44-53. Springer, 2012. Google Scholar
  39. Andrew Chi-Chih Yao. New algorithms for bin packing. Journal of the ACM (JACM), 27(2):207-227, 1980. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact