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 })\) for the migration factor. We establish a nearly matching 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 nand 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).
Similar content being viewed by others
References
Balogh, J., Békési, J., Dósa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. CoRR arXiv:1707.01728 (2017)
Balogh, J., Békési, J., Dósa, G., Sgall, J., van Stee, R.: The optimal absolute ratio for online bin packing. In: SODA, pp. 1425–1438. SIAM (2015)
Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. In: Workshop on Approximation and Online Algorithms (WAOA), LNCS, vol. 6534, pp. 25–36 (2010)
Balogh, J., Békési, J., Galambos, G., Reinelt, G.: Lower bound for the online bin packing problem with restricted repacking. SIAM J. Comput. 38(1), 398–410 (2008)
Beling, P., Megiddo, N.: Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205(1–2), 307–316 (1998)
Beloglazov, A., Buyya, R.: Energy efficient allocation of virtual machines in cloud data centers. In: 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, CCGrid 2010, pp. 577–578 (2010)
Berndt, S., Jansen, K., Klein, K.: Fully dynamic bin packing revisited. In: APPROX-RANDOM, LIPIcs, vol. 40, pp. 135–151. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
Bobroff, N., Kochut, A., Beaty, K.: Dynamic placement of virtual machines for managing SLA violations. In: 10th IFIP/IEEE International Symposium on Integrated Network Management, IM 2007, pp. 119–128 (2007)
Brown, D.: A lower bound for on-line one-dimensional bin packing algorithms. Technical Report R-864, Coordinated Science Laboratory University of Illinois Urbana (1979)
Chan, J., Lam, T., Wong, P.: Dynamic bin packing of unit fractions items. Theor. Comput. Sci. 409(3), 521–529 (2008)
Chan, J., Wong, P., Yung, F.: On dynamic bin packing: an improved lower bound and resource augmentation analysis. Algorithmica 53(2), 172–206 (2009)
Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63–79 (2017)
Coffman, E., Garey, M., Johnson, D.: Dynamic bin packing. SIAM J. Comput. 12(2), 227–258 (1983)
Daudjee, K., Kamali, S., López-Ortiz, A.: On the online fault-tolerant server consolidation problem. In: 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, pp. 12–21 (2014)
Eisemann, K.: The trim problem. Manag. Sci. 3(3), 279–284 (1957)
Epstein, L., Levin, A.: A robust APTAS for the classical bin packing problem. Math. Program. 119(1), 33–49 (2009)
Epstein, L., Levin, A.: Robust approximation schemes for cube packing. SIAM J. Optim. 23(2), 1310–1343 (2013)
Feldkord, B., Feldotto, M., Riechers, S.: A tight approximation for fully dynamic bin packing without bundling. In: ICALP (2018)
Gambosi, G., Postiglione, A., Talamo, M.: Algorithms for the relaxed online bin-packing model. J. Comput. 30(5), 1532–1551 (2000)
Gupta, A., Guruganesh, G., Kumar, A., Wajc, D.: Fully-dynamic bin packing with limited repacking. In: ICALP (2018)
Heydrich, S., van Stee, R.: Beating the harmonic lower bound for online bin packing. In: ICALP, LIPIcs, vol. 55, pp. 41:1–41:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)
Ivković, Z., Lloyd, E.: Partially dynamic bin packing can be solved within \(1 + \epsilon \) in (amortized) polylogarithmic time. Inf. Process. Lett. 63(1), 45–50 (1997)
Ivković, Z., Lloyd, E.: Fully dynamic algorithms for bin packing: being (mostly) myopic helps. SIAM J. Comput. 28(2), 574–611 (1998)
Ivković, Z., Lloyd, E.: Fully dynamic bin packing. In: Fundamental Problems in Computing, pp. 407–434. Springer (2009)
Jansen, K., Klein, K.: A robust AFPTAS for online bin packing with polynomial migration. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 589–600 (2013)
Jansen, K., Klein, K., Kosche, M., Ladewig, L.: Online strip packing with polynomial migration. In: APPROX-RANDOM, LIPIcs, vol. 81, pp. 13:1–13:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)
Jansen, K., Kraft, S.E.J.: A faster FPTAS for the unbounded knapsack problem. In: IWOCA, Lecture Notes in Computer Science, vol. 9538, pp. 274–286. Springer (2015)
Johnson, D.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272–314 (1974)
Johnson, D., Demers, A., Ullman, J., Garey, M., Graham, R.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)
Jung, G., Joshi, K., Hiltunen, M., Schlichting, R., Pu, C.: Generating adaptation policies for multi-tier applications in consolidated server environments. In: 2008 International Conference on Autonomic Computing, ICAC 2008, 2–6 June 2008, Chicago, Illinois, USA, pp. 23–32 (2008)
Jung, G., Joshi, K., Hiltunen, M., Schlichting, R., Pu, C.: A cost-sensitive adaptation engine for server consolidation of multitier applications. In: Proceedings of 10th International Middleware Conference on Middleware 2009, ACM/IFIP/USENIX, pp. 163–183 (2009)
Karmarkar, N., Karp, R.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 312–320. IEEE Computer Society (1982)
Lee, C., Lee, D.: A simple on-line bin-packing algorithm. J. ACM (JACM) 32(3), 562–572 (1985)
Li, Y., Tang, X., Cai, W.: On dynamic bin packing for resource allocation in the cloud. In: 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, pp. 2–11 (2014)
Liang, F.: A lower bound for on-line bin packing. Inf. Process. Lett. 10(2), 76–79 (1980)
Park, J., Savagaonkar, U.R., Chong, E., Siegel, H., Jones, S.: Efficient resource allocation for QoS channels in MF-TDMA satellite systems. In: Proceedings of Conference on 21st Century Military Communications, MILCOM 2000, vol. 2, pp. 645–649. IEEE (2000)
Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Math. Oper. Res. 34(2), 481–498 (2009)
Seiden, S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002)
Skutella, M., Verschae, J.: Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures. Math. Oper. Res. 41(3), 991–1021 (2016)
Srikantaiah, S., Kansal, A., Zhao, F.: Energy aware consolidation for cloud computing. In: Proceedings of the 2008 Conference on Power Aware Computing and Systems, HotPower’08, p. 10 (2008)
Stolyar, A.: An infinite server system with general packing constraints. Oper. Res. 61(5), 1200–1217 (2013)
Stolyar, A., Zhong, Y.: 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, pp. 41–52. ACM (2013)
Ullman, J.: The Performance of a Memory Allocation Algorithm. Technical Report. Princeton University (1971)
de la Fernandez Vega, W., Lueker, G.: Bin packing can be solved within \(1+ \epsilon \) in linear time. Combinatorica 1(4), 349–355 (1981)
Verma, A., Ahuja, P., Neogi, A.: pMapper: power and migration cost aware application placement in virtualized systems. In: Proceedings of the 9th International Middleware Conference on Middleware 2008, ACM/IFIP/USENIX, pp. 243–264 (2008)
Vliet, A.: An improved lower bound for on-line bin packing algorithms. Inf. Process. Lett. 43(5), 277–284 (1992)
Yao, A.: New algorithms for bin packing. J. ACM (JACM) 27(2), 207–227 (1980)
Acknowledgements
We would like to thank Till Tantau for his valuable comments and suggestions to improve the presentation of the paper. We also thank the anonymous reviewers for their detailed and valuable feedback.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by DFG Project, Entwicklung und Analyse von effizienten polynomiellen Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme, Ja 612/14-1 and Ja 612/14-2.
A preliminary version of this work has appeared at APPROX/RANDOM 2015 as [7].
Rights and permissions
About this article
Cite this article
Berndt, S., Jansen, K. & Klein, KM. Fully dynamic bin packing revisited. Math. Program. 179, 109–155 (2020). https://doi.org/10.1007/s10107-018-1325-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-018-1325-x