Top

Published in:

2023 | OriginalPaper | Chapter

New Results in Priority-Based Bin Packing

Authors : K. Subramani, P. Wojciechowski, Alvaro Velasquez

Published in: Algorithmic Aspects of Cloud Computing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we discuss new algorithmic results for bin minimization in the subset-constrained variant of Priority-based bin packing (PBBP-SC). This problem was introduced in [21], as an abstract model for capturing certain issues in database migration and palleting. This paper focuses on new fine-grained complexity results for the bin minimization problem (BMP) under two distinct parameterizations. We also provide a detailed empirical analysis of integer programming formulations for the problems discussed in this paper.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter MAGMA: Proposing a Massive Historical Graph Management System

next chapter More Sparking Soundex-Based Privacy-Preserving Record Linkage

Acikalin, U.U., Caskurlu, B., Wojciechowski, P., Subramani, K.: New results on test-cost minimization in database migration. In: D’Angelo, G., Michail, O. (eds.) ALGOCLOUD 2021. LNCS, vol. 13084, pp. 38–55. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-93043-1_3CrossRef

Ballew, B.: The distributor’s three-dimensional pallet-packing problem: a mathematical formulation and heuristic solution approach. Master’s thesis, Air Force Institute of Technology, March 2000

Borradaile, G., Heeringa, B., Wilfong, G.T.: The knapsack problem with neighbour constraints. J. Discrete Algorithms 16, 224–235 (2012)MathSciNetCrossRefMATH

Bringmann, K.: Fine-grained complexity theory (tutorial). In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13–16, 2019, Berlin, Germany, vol. 126 of LIPIcs, pp. 4:1–4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.): WAE 2001. LNCS, vol. 2141. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44688-5CrossRef

Cygan, M., Fomin, F.V., Kowalik, Ł, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3CrossRefMATH

Drumm, C., Schmitt, M., Do, H.H., Rahm, E.: Quickmig: automatic schema matching for data migration projects. In: Proceedings of the Sixteenth ACM Conference on Information and Knowledge Management, CIKM 2007, Lisbon, Portugal, 6–10 November 2007, pp. 107–116 (2007)

Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Theory of Parameterized Preprocessing. Cambridge University Press, Kernelization (2019)

Gandhi, R., Halldórsson, M.M., Kortsarz, G., Shachnai, H.: Improved results for data migration and open shop scheduling. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 658–669. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_56CrossRefMATH

10.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco (1979)MATH

11.

Goldman, R., McHugh, J., Widom, J.: From semistructured data to XML: migrating the lore data model and query language. In: ACM SIGMOD Workshop on The Web and Databases, WebDB 1999, Philadelphia, Pennsylvania, USA, 3–4 June 1999. Informal Proceedings, pp. 25–30 (1999)

12.

Golubchik, L., Khuller, S., Kim, Y.A., Shargorodskaya, S., (Justin) Wan, Y.-C.: Data migration on parallel disks. In: Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, 14–17 September 2004, Proceedings, pp. 689–701 (2004)

13.

Hall, J., Hartline, J.D., Karlin, A.R., Saia, J., Wilkes, J.: On algorithms for efficient data migration. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7–9 January 2001, Washington, DC, USA, pp. 620–629 (2001)

14.

Hodgson, T.J.: A combined approach to the pallet loading problem. A I I E Transactions 14(3), 175–182 (1982)CrossRef

15.

Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39–49 (2013)MathSciNetCrossRefMATH

16.

Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990)MATH

17.

Martins, G.H.A., Dell, R.F.: Solving the pallet loading problem. Eur. J. Oper. Res. 184(2), 429–440 (2008)

18.

Subramani, K., Caskurlu, B., Acikalin, U.U.: Security-aware database migration planning. In: Brandic, I., Genez, T.A.L., Pietri, I., Sakellariou, R. (eds.) ALGOCLOUD 2019. LNCS, vol. 12041, pp. 103–121. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58628-7_7CrossRef

19.

Subramani, K., Caskurlu, B., Velasquez, A.: Minimization of testing costs in capacity-constrained database migration. In: Disser, Y., Verykios, V.S. (eds.) ALGOCLOUD 2018. LNCS, vol. 11409, pp. 1–12. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19759-9_1CrossRef

20.

Tovey, C.A.: A simplified np-complete satisfiability problem. Discret. Appl. Math. 8(1), 85–89 (1984)MathSciNetCrossRefMATH

21.

Wojciechowski, P., Subramani, K., Velasquez, A., Caskurlu, B.: Algorithmic analysis of priority-based bin packing. In: Mudgal, A., Subramanian, C.R. (eds.) CALDAM 2021. LNCS, vol. 12601, pp. 359–372. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-67899-9_29CrossRef

Title: New Results in Priority-Based Bin Packing
Authors: K. Subramani
P. Wojciechowski
Alvaro Velasquez
Publisher: Springer International Publishing
Book: Algorithmic Aspects of Cloud Computing
Print ISBN: 978-3-031-33436-8

Electronic ISBN: 978-3-031-33437-5

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-33437-5_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner