nach oben

Journal of Combinatorial Optimization

Erschienen in:

23.06.2016

A new upper bound for the online square packing problem in a strip

verfasst von: Guosong Yu, Yanling Mao, Jiaoliao Xiao

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we consider the online problem of packing a list of squares into one strip of width 1 and infinite length without overlap so as to minimize the required height of the packing. We derive an upper bound 5 on the competitive ratio for this problem.

Vorheriger Artikel A new effective branch-and-bound algorithm to the high order MIMO detection problem

Nächster Artikel On irreducible no-hole L(2, 1)-coloring of subdivision of graphs

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 "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

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

Brown DJ, Baker BS, Katseff HP (1982) Lower bounds for online two-dimensional packing algorithms. Acta Informatica 18(2):207–225MathSciNetCrossRefMATH

Baker BS, Coffman EG, Rivest RL (1980) Orthogonal packings in two dimensions. SIAM J Comput 9:846–855MathSciNetCrossRefMATH

Baker BS, Schwarz JS (1983) Shelf algorithms for two-dimensional packing problems. SIAM J Comput 12(3):508–525MathSciNetCrossRefMATH

Coffman EG Jr, Garey MR, Johnson DS, Tarjan RE (1980) Performance bounds for leveloriented two-dimensional packing algorithms. SIAM J Comput 9(4):808–826MathSciNetCrossRefMATH

Coppersmith D, Raghavan P (1989) Multidimensional online bin packing. Algorithms and worst case analysis. Oper Res Lett 8:17–20MathSciNetCrossRefMATH

Epstein L, van Stee R (2005) Online square and cube packing. Acta Informatica 41(9):595–606MathSciNetCrossRefMATH

Han X, Iwama K, Ye D, Zhang G (2007) Strip packing vs. bin packing. AAIM 2007:358–367MATH

Harren R, Kern W (2015) Improved lower bound for online strip packing. Theory Comput Syst 56(1):41–72MathSciNetCrossRefMATH

Hurink, J., Paulus, J.(2007). Online algorithm for parallel job scheduling and strip packing. In: WAOA: Proceedings of 5th Workshop on Approximation and Online Algorithms, pp 67–74

Hurink J, Paulus J (2008) Online scheduling of parallel jobs on two machines is 2-competitive. Oper Res Lett 36(1):51–56MathSciNetCrossRefMATH

Han X, Ye D, Zhou Y (2010) A note on online hypercube packing. Cent Eur J Oper Res 18:221–239MathSciNetCrossRefMATH

Johannes B (2006) Scheduling parallel jobs to minimize the makespan. J Sched 9(5):433–452MathSciNetCrossRefMATH

Kern W, Paulus J (2013) A tight analysis of Brown–Baker–Katseff sequences for online strip packing. J Comb Opt 26(2):333–344MathSciNetCrossRefMATH

Lee CC, Lee DT (1985) A simple on-line bin-packing algorithm. J ACM 32:562–572MathSciNetCrossRefMATH

Marty, M.R., Hill, M.D.(2007). Virtual hierarchies to support server consolidation. In: Proceedings of the 34th annual international conference on computer architecture, pp 46–56

Ramanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305–326MathSciNetCrossRefMATH

Richey MB (1991) Improved bounds for harmonic-based bin packing algorithms. Discrete Appl Math 34:203–227MathSciNetCrossRefMATH

Seiden SS (2002) On the online bin packing problem. J ACM 49:640–671MathSciNetCrossRefMATH

Seiden SS, van Stee R (2003) New bounds for multi-dimensional packing. Algorithmica 36(3):261–293MathSciNetCrossRefMATH

Ye D, Han X, Zhang G (2009) A note on online strip packing. J Comb Optim 17(4):417–423MathSciNetCrossRefMATH

Ye D, Han X, Zhang G (2009) On-line multiple-strip packing. In: COCOA 2009, 155–165

Yu G, Mao Y, Xiao J (2016) A new lower bound for online strip packing. Eur J Oper Res 250(3):754–759MathSciNetCrossRefMATH

Titel: A new upper bound for the online square packing problem in a strip
verfasst von: Guosong Yu
Yanling Mao
Jiaoliao Xiao
Publikationsdatum: 23.06.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-016-0046-4

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2017

The solution of a generalized secretary problem via analytic expressions

Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable

Optimal RSUs placement with delay bounded message dissemination in vehicular networks

Even factors of graphs

On irreducible no-hole L(2, 1)-coloring of subdivision of graphs

Lambda number for the direct product of some family of graphs

Premium Partner