Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Algorithms for the Evacuation Route Planning Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Black and White Bin Packing Revisited

Authors : Jing Chen, Xin Han, Wolfgang Bein, Hing-Fung Ting

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The black and white bin packing problem is a variant of the classical bin packing problem, where in addition to a size, each item also has a color (black or white), and in each bin the colors of items must alternate. The problem has been studied extensively, but the best competitive online algorithm has competitiveness of 3. The competitiveness of 3 can be forced even when the sizes of items are ‘halved’, i.e. the sizes are restricted to be in (0, 1 / 2]. We give the first ‘better than 3’ competitive algorithm for the problem for the case that item sizes are in the range (0, 1 / 2]; our algorithm has competitiveness \(\frac{8}{3}\).

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 Directed Pathwidth and Palletizers
next chapter Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
Literature
1.
Bálogh, J., Békési, J., Dósa, G., Epstein, L., Kellerer, H., Tuza, Z.: Online results for black and white bin packing. Theory Comput. Syst. 56, 137–155 (2015)MathSciNetCrossRefMATH
2.
Balogh, J., Békési, J., Dosa, G., Kellerer, H., Tuza, Z.: Black and white bin packing. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 131–144. Springer, Heidelberg (2013) CrossRef
3.
Bálogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440–441, 1–13 (2012)MathSciNetCrossRefMATH
4.
Boyar, J., Dósa, G., Epstein, L.: On the absolute approximation ratio for First Fit and related Results. Discrete Appl. Math. 160(13–14), 1914–1923 (2012)MathSciNetCrossRefMATH
5.
Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms. PWS Publishing Company (1997)
6.
Dósa, G., Sgall, J.: First fit bin packing: a tight analysis. In: Proceedings of STACS 2013, LIPICS, vol. 20, pp. 538–549 (2013)
7.
Dósa, G., Epstein, L.: Colorful bin packing. In: Ravi, R., Gørtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 170–181. Springer, Heidelberg (2014) CrossRef
8.
Böhm, M., Sgall, J., Veselý, P.: Online colored bin packing. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 35–46. Springer, Heidelberg (2015)
9.
Garey, M.R., Johnson, D.S.: “Strong” NP-completeness results: motivation, examples, and implications. J. ACM 25(3), 499–508 (1978)MathSciNetCrossRefMATH
10.
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pp. 312–320 (1982)
11.
12.
13.
Ullman, J.D.: The performance of a memory allocation algorithm. Technical report 100, Princeton University, Princeton 695 (1971)
14.
Veselý, P.: Competitiveness of fit algorithms for black and white bin packing. In: Middle-European Conference on Applied Theoretical Computer Science (2013)
15.
Xia, B.Z., Tan, Z.Y.: Tighter bound of the First Fit algorithm for the bin-packing problem. Discrete Appl. Math. 158(15), 1668–1675 (2010)MathSciNetCrossRefMATH
Metadata
Title
Black and White Bin Packing Revisited
Authors
Jing Chen
Xin Han
Wolfgang Bein
Hing-Fung Ting
Copyright Year
2015
Book
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-26625-1

Electronic ISBN: 978-3-319-26626-8

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26626-8_4

Premium Partner

    Image Credits