nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

18. Bin-Packing

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Suppose we have n objects, each of a given size, and some bins of equal capacity. We want to assign the objects to the bins, using as few bins as possible. Of course the total size of the objects assigned to one bin should not exceed its capacity.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel The Knapsack Problem

Nächstes Kapitel Multicommodity Flows and Edge-Disjoint Paths

Coffman, E.G., Garey, M.R., and Johnson, D.S. [1996]: Approximation algorithms for bin-packing; a survey. In: Approximation Algorithms for NP-Hard Problems (D.S. Hochbaum, ed.), PWS, Boston, 1996

Baker, B.S. [1985]: A new proof for the First-Fit Decreasing bin-packing algorithm. Journal of Algorithms 6 (1985), 49–70

Bansal, N., Correa, J.R., Kenyon, C., and Sviridenko, M. [2006]: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of Operations Research 31 (2006), 31–49

Bansal, N. and Khan, A. [2014]: Improved approximation algorithm for two-dimensional bin packing. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (2014), 13–25

Caprara, A. [2008]: Packing d-dimensional bins in d stages. Mathematics of Operations Research 33 (2008), 203–215

Dósa, G., Li, R., Han, X., and Tuza, Z. [2013]: Tight absolute bound for First Fit Descreasing bin-packing: FFD(L) ≤ 11∕9 OPT(L) + 6∕9. Theoretical Computer Science 510 (2013), 13–61

Dósa, G., and Sgall, J. [2013]: First fit bin packing: a tight analysis. Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (2013), 538–549

Eisemann, K. [1957]: The trim problem. Management Science 3 (1957), 279–284

Eisenbrand, F., and Shmonin, G. [2006]: Carathéodory bounds for integer cones. Operations Research Letters 34 (2006), 564–568

Fernandez de la Vega, W., and Lueker, G.S. [1981]: Bin packing can be solved within 1 + ε in linear time. Combinatorica 1 (1981), 349–355

Garey, M.R., Graham, R.L., Johnson, D.S., and Yao, A.C. [1976]: Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory A 21 (1976), 257–298

Garey, M.R., and Johnson, D.S. [1975]: Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing 4 (1975), 397–411

Garey, M.R., and Johnson, D.S. [1979]: Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, San Francisco 1979, p. 127

Gilmore, P.C., and Gomory, R.E. [1961]: A linear programming approach to the cutting-stock problem. Operations Research 9 (1961), 849–859

Goemans, M.X., and Rothvoß, T. [2014]: Polynomiality for bin packing with a constant number of item types. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (2014), 830–839

Graham, R.L. [1966]: Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal 45 (1966), 1563–1581

Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G. [1979]: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Discrete Optimization II; Annals of Discrete Mathematics 5 (P.L. Hammer, E.L. Johnson, B.H. Korte, eds.), North-Holland, Amsterdam 1979, pp. 287–326

Hochbaum, D.S., and Shmoys, D.B. [1987]: Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM 34 (1987), 144–162

Hoberg, R., and Rothvoß, T. [2017]: A logarithmic additive integrality gap for bin packing. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (2017), 2616–2625

Horowitz, E., and Sahni, S.K. [1976]: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM 23 (1976), 317–327

Jansen, K., Prädel, L., and Schwarz, U.M. [2009]: Two for one: tight approximation of 2D bin packing. In: Algorithms and Data Structures – Proceedings of the 11th Algorithms and Data Structures Symposium; LNCS 5664 (F. Dehne, M. Gavrilova, J.-R. Sack, C.D. Tóth, eds.), Springer, Berlin 2009, pp. 399–410

Johnson, D.S. [1973]: Near-Optimal Bin Packing Algorithms. Doctoral Thesis, Dept. of Mathematics, MIT, Cambridge, MA, 1973

Johnson, D.S. [1974]: Fast algorithms for bin-packing. Journal of Computer and System Sciences 8 (1974), 272–314

Johnson, D.S. [1982]: The NP-completeness column; an ongoing guide. Journal of Algorithms 3 (1982), 288–300, Section 3

Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., and Graham, R.L. [1974]: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing 3 (1974), 299–325

Karmarkar, N., and Karp, R.M. [1982]: An efficient approximation scheme for the one-dimensional bin-packing problem. Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (1982), 312–320

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. [1993]: Sequencing and scheduling: algorithms and complexity. In: Handbooks in Operations Research and Management Science; Vol. 4 (S.C. Graves, A.H.G. Rinnooy Kan, P.H. Zipkin, eds.), Elsevier, Amsterdam 1993

Lenstra, H.W. [1983]: Integer Programming with a fixed number of variables. Mathematics of Operations Research 8 (1983), 538–548

Papadimitriou, C.H. [1994]: Computational Complexity. Addison-Wesley, Reading 1994, pp. 204–205

Plotkin, S.A., Shmoys, D.B., and Tardos, É. [1995]: Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research 20 (1995), 257–301

Queyranne, M. [1986]: Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Operations Research Letters 4 (1986), 231–234

Seiden, S.S. [2002]: On the online bin packing problem. Journal of the ACM 49 (2002), 640–671

Simchi-Levi, D. [1994]: New worst-case results for the bin-packing problem. Naval Research Logistics 41 (1994), 579–585

van Vliet, A. [1992]: An improved lower bound for on-line bin packing algorithms. Information Processing Letters 43 (1992), 277–284

Yue, M. [1991]: A simple proof of the inequality \(FFD(L) \leq \frac{11} {9} \mathop{ \mathrm{OPT}}(L) + 1,\forall L\), for the FFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 7 (1991), 321–331

Titel: Bin-Packing
verfasst von: Bernhard Korte
Jens Vygen
Verlag: Springer Berlin Heidelberg
Buch: Combinatorial Optimization
Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-662-56039-6_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"