Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 8/2019

09.03.2019

Lower Bounds for Several Online Variants of Bin Packing

verfasst von: János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

Erschienen in: Theory of Computing Systems | Ausgabe 8/2019

Einloggen

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

search-config
loading …

Abstract

We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75.
Vorheriger Artikel Guest Editorial: Special Issue on Approximation and Online Algorithms
Nächster Artikel On Conceptually Simple Algorithms for Variants of Online Bipartite Matching

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
Literatur
1.
Angelopoulos, S., Du̇rr, C., Kamali, S., Renault, M.P., Rosėn, A.: Online bin packing with advice of small size. In: Proceedings of The 14th International Symposium Algorithms and Data Structures (WADS’15), pp. 40–53 (2015)
2.
Babel, L., Chen, B., Kellerer, H., Kotov, V.: Algorithms for on-line bin-packing problems with cardinality constraints. Discret. Appl. Math. 143(1-3), 238–251 (2004)MathSciNetMATHCrossRef
3.
4.
Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: Online bin packing with cardinality constraints resolved. The Computing Res. Rep. (CoRR), arXiv:1608.​06415 (2016)
5.
Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: Online bin packing with cardinality constraints resolved. In: Proceedings of the 25th Annual European Symposium on Algorithms (ESA’17), pp. 10:1–10:14 (2017)
6.
Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: Proceedings of the 26th annual European symposium on algorithms (ESA18), pp 5:1–5:14 (2018)
7.
Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. The Computing Res. Rep. (CoRR), arXiv:1807.​05554 (2018)
8.
Balogh, 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)MathSciNetMATHCrossRef
9.
Bansal, N., Correa, J., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions Inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31–49 (2006)MathSciNetMATHCrossRef
10.
Békési, J., Dósa, Gy., Epstein, L.: Bounds for online bin packing with cardinality constraints. Inf. Comput. 249, 190–204 (2016)MathSciNetMATHCrossRef
11.
Blitz, D.: Lower bounds on the asymptotic worst-case ratios of on-line bin packing algorithms. M.Sc. thesis, University of Rotterdam, number 114682 (1996)
12.
13.
Coppersmith, D., Raghavan, P.: Multidimensional online bin packing: Algorithms and worst case analysis. Oper. Res. Lett. 8(1), 17–20 (1989)MathSciNetMATHCrossRef
14.
15.
Epstein, L., Imreh, Cs., Levin, A.: Class constrained bin packing revisited. Theor. Comput. Sci. 411(34-36), 3073–3089 (2010)MathSciNetMATHCrossRef
16.
17.
18.
19.
Epstein, L., Tushia, A.: Work in progress (2018)
20.
Fujiwara, H., Kobayashi, K.: Improved lower bounds for the online bin packing problem with cardinality constraints. J. Comb. Optim. 29(1), 67–87 (2015)MathSciNetMATHCrossRef
21.
22.
Heydrich, S., van Stee, R.: Improved Lower Bounds for Online Hypercube Packing. The Computing Res. Rep. (CoRR), arXiv:1607.​01229 (2016)
23.
24.
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256–278 (1974)MathSciNetMATHCrossRef
25.
26.
Krause, K.L., Shen, V.Y., Schwetman, H.D.: Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J. ACM 22(4), 522–550 (1975)MathSciNetMATHCrossRef
27.
28.
29.
30.
31.
Shachnai, H., Tamir, T.: Polynomial time approximation schemes for class-constrained packing problems. J. Sched. 4(6), 313–338 (2001)MathSciNetMATHCrossRef
32.
Ullman, J.D.: The Performance of a Memory Allocation Algorithm. Technical Report, vol. 100. Princeton University, Princeton (1971)
33.
van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 277–284 (1992)MATHCrossRef
34.
Xavier, E.C., Miyazawa, F.K.: The class constrained bin packing problem with applications to video-on-demand. Theor. Comput. Sci. 393(1-3), 240–259 (2008)MathSciNetMATHCrossRef
35.
Metadaten
Titel
Lower Bounds for Several Online Variants of Bin Packing
verfasst von
János Balogh
József Békési
György Dósa
Leah Epstein
Asaf Levin
Publikationsdatum
09.03.2019
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 8/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-019-09915-1

Weitere Artikel der Ausgabe 8/2019

Theory of Computing Systems 8/2019 Zur Ausgabe

OriginalPaper

On Conceptually Simple Algorithms for Variants of Online Bipartite Matching

OriginalPaper

Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs

EditorialNotes

Guest Editorial: Special Issue on Approximation and Online Algorithms

OriginalPaper

On-line Search in Two-Dimensional Environment