Document Open Access Logo

Fully Dynamic Bin Packing Revisited

Authors Sebastian Berndt, Klaus Jansen, Kim-Manuel Klein

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.135.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Sebastian Berndt
Klaus Jansen
Kim-Manuel Klein

Cite AsGet BibTex

Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully Dynamic Bin Packing Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 135-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.135

Abstract

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1 + epsilon for the number of bins, a relatively simple argument proves a lower bound of Omega(1/epsilon) of the migration factor. We establish a fairly close upper bound of O(1/epsilon^4 log(1/epsilon)) using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items n and in 1/epsilon. The previous best trade-off was for an asymptotic competitive ratio of 5/4 for the bins (rather than 1+epsilon) and needed an amortized number of O(log n) repackings (while in our scheme the number of repackings is independent of n and non-amortized).
Keywords
  • online
  • bin packing
  • migration factor
  • robust
  • AFPTAS

Metrics

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

References

  1. J. Balogh, J. Békési, and G. Galambos. New lower bounds for certain classes of bin packing algorithms. In Workshop on Approximation and Online Algorithms(WAOA), volume 6534 of LNCS, pages 25-36, 2010. Google Scholar
  2. J. Balogh, J. Békési, G. Galambos, and G. Reinelt. Lower bound for the online bin packing problem with restricted repacking. SIAM Journal on Computing, 38(1):398-410, 2008. Google Scholar
  3. A. Beloglazov and R. Buyya. Energy efficient allocation of virtual machines in cloud data centers. In 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, CCGrid 2010, pages 577-578, 2010. Google Scholar
  4. N. Bobroff, A. Kochut, and K.A. Beaty. Dynamic placement of virtual machines for managing SLA violations. In Integrated Network Management, IM 2007. 10th IFIP/IEEE International Symposium on Integrated Network Management, pages 119-128, 2007. Google Scholar
  5. D.J. Brown. A lower bound for on-line one-dimensional bin packing algorithms. Technical Report R-864, Coordinated Sci Lab Univ of Illinois Urbana, 1979. Google Scholar
  6. J.W. Chan, T. Lam, and P.W.H. Wong. Dynamic bin packing of unit fractions items. Theoretical Computer Science, 409(3):521-529, 2008. Google Scholar
  7. J.W. Chan, P.W.H. Wong, and F.C.C. Yung. On dynamic bin packing: An improved lower bound and resource augmentation analysis. Algorithmica, 53(2):172-206, 2009. Google Scholar
  8. E.G. Coffman, M.R. Garey, and D.S. Johnson. Dynamic bin packing. SIAM Journal on Computing, 12(2):227-258, 1983. Google Scholar
  9. Khuzaima D., Shahin K., and Alejandro L. On the online fault-tolerant server consolidation problem. In 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'14, pages 12-21, 2014. Google Scholar
  10. K. Eisemann. The Trim Problem. Management Science, 3(3):279-284, 1957. Google Scholar
  11. L. Epstein and A. Levin. A robust APTAS for the classical bin packing problem. Mathematical Programming, 119(1):33-49, 2009. Google Scholar
  12. L. Epstein and A. Levin. Robust approximation schemes for cube packing. SIAM Journal on Optimization, 23(2):1310-1343, 2013. Google Scholar
  13. W. Fernandez de la Vega and G.S. Lueker. Bin packing can be solved within 1+ ε in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  14. G. Gambosi, A. Postiglione, and M. Talamo. Algorithms for the relaxed online bin-packing model. SIAM Journal on Computing, 30(5):1532-1551, 2000. Google Scholar
  15. Z. Ivković and E.L. Lloyd. Partially dynamic bin packing can be solved within 1 + ε in (amortized) polylogarithmic time. Information Processing Letter, 63(1):45-50, 1997. Google Scholar
  16. Z. Ivković and E.L. Lloyd. Fully dynamic algorithms for bin packing: Being (mostly) myopic helps. SIAM Journal on Computing, 28(2):574-611, 1998. Google Scholar
  17. Z. Ivković and E.L. Lloyd. Fully dynamic bin packing. In Fundamental Problems in Computing, pages 407-434. Springer, 2009. Google Scholar
  18. K. Jansen and K. Klein. A robust AFPTAS for online bin packing with polynomial migration. In International Colloquium on Automata, Languages, and Programming(ICALP), pages 589-600, 2013. Google Scholar
  19. D.S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8(3):272-314, 1974. Google Scholar
  20. D.S. Johnson, A. Demers, J.D. Ullman, M.R. Garey, and R.L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325, 1974. Google Scholar
  21. D.S. Johnson, A.J. Demers, J.D. Ullman, M.R. Garey, and R.L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4):299-325, 1974. Google Scholar
  22. G. Jung, K.R. Joshi, M.A. Hiltunen, R.D. Schlichting, and C. Pu. Generating adaptation policies for multi-tier applications in consolidated server environments. In 2008 International Conference on Autonomic Computing, ICAC 2008, June 2-6, 2008, Chicago, Illinois, USA, pages 23-32, 2008. Google Scholar
  23. G. Jung, K.R. Joshi, M.A. Hiltunen, R.D. Schlichting, and C. Pu. A cost-sensitive adaptation engine for server consolidation of multitier applications. In Middleware 2009, ACM/IFIP/USENIX, 10th International Middleware Conference, Proceedings, pages 163-183, 2009. Google Scholar
  24. N. Karmarkar and R.M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 312-320. IEEE Computer Society, 1982. Google Scholar
  25. C.C. Lee and D. Lee. A simple on-line bin-packing algorithm. Journal of the ACM (JACM), 32(3):562-572, 1985. Google Scholar
  26. Y. Li, X. Tang, and W. Cai. On dynamic bin packing for resource allocation in the cloud. In 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'14, pages 2-11, 2014. Google Scholar
  27. F.M. Liang. A lower bound for on-line bin packing. Information processing letters, 10(2):76-79, 1980. Google Scholar
  28. J.M. Park, Uday R. Savagaonkar, E.K.P. Chong, H.J. Siegel, and S.D. Jones. Efficient resource allocation for qos channels in mf-tdma satellite systems. In MILCOM 2000. 21st Century Military Communications Conference Proceedings, volume 2, pages 645-649. IEEE, 2000. Google Scholar
  29. P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Google Scholar
  30. S.S. Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640-671, 2002. Google Scholar
  31. M. Skutella and J. Verschae. A robust PTAS for machine covering and packing. In European Symposium on Algorithms(ESA), volume 6346 of LNCS, pages 36-47, 2010. Google Scholar
  32. S. Srikantaiah, A. Kansal, and F. Zhao. Energy aware consolidation for cloud computing. In Proceedings of the 2008 Conference on Power Aware Computing and Systems, HotPower'08, pages 10-10, 2008. Google Scholar
  33. A.L. Stolyar. An infinite server system with general packing constraints. Operations Research, 61(5):1200-1217, 2013. Google Scholar
  34. A.L. Stolyar and Y. Zhong. A large-scale service system with packing constraints: Minimizing the number of occupied servers. In Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems, pages 41-52. ACM, 2013. Google Scholar
  35. J.D. Ullman. The Performance of a Memory Allocation Algorithm. Technical report. Princeton University, 1971. Google Scholar
  36. A. Verma, P. Ahuja, and A. Neogi. pmapper: Power and migration cost aware application placement in virtualized systems. In Middleware 2008, ACM/IFIP/USENIX 9th International Middleware Conference, Proceedings, pages 243-264, 2008. Google Scholar
  37. A. Vliet. An improved lower bound for on-line bin packing algorithms. Information Processing Letters, 43(5):277-284, 1992. Google Scholar
  38. Prudence WH Wong, Fencol CC Yung, and Mihai Burcea. An 8/3 lower bound for online dynamic bin packing. In Algorithms and Computation, pages 44-53. Springer, 2012. Google Scholar
  39. A.C. 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 Imprint Privacy Contact