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
Theory of Computing Systems
Published in: Theory of Computing Systems 8/2018

12-04-2018

Online Bin Packing with Advice of Small Size

Authors: Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc P. Renault, Adi Rosén

Published in: Theory of Computing Systems | Issue 8/2018

Log in

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

search-config
loading …

Abstract

In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and has a competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. (Algorithmica 74(1), 507–527 2016) so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, improving on the lower bound of 9/8 from Boyar et al.
previous article Primitivity, Uniform Minimality, and State Complexity of Boolean Operations
next article The Most Points Connected-Covering Problem with Two Disks

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

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
Footnotes
1
Technically, the statement of Lemma 16 is very similar to Lemma 9 in [13]. We note, however, that the latter is correct only when the number of 0s is n/2. To avoid any ambiguity, the statement of Lemma 16 is parameterized by β, as opposed to Lemma 9 in [13].
 
Literature
1.
Adamaszek, A., Renault, M.P., Rosėn, A., van Stee, R.: Reordering buffer management with advice. J. Schedul. (2016)
2.
Angelopoulos, S., Dürr, C., Kamali, S., Renault, M.P., Rosén, A.: Online bin packing with advice of small size. In: Dehne, F., Sack, J., Stege, U. (eds.) Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, Lecture Notes in Computer Science, vol. 9214, pp 40–53. Springer (2015)
3.
Asgeirsson, E., Ayesta, U., Coffman, E., Etra, J., Momcilovic, P., Phillips, D., Vokhshoori, V., Wang, Z., Wolfe, J.: Closed on-line bin packing. Acta Cybernet. 15(3), 361–367 (2002)MathSciNetMATH
4.
Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440–441, 1–13 (2012)MathSciNetCrossRefMATH
5.
Bianchi, M.P., Böckenhauer, H., Brülisauer, T., Komm, D., Palano, B.: Online minimum spanning tree with advice - (extended abstract). In: Freivalds, R.M., Engels, G., Catania, B. (eds.) SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9587, pp 195–207. Springer (2016)
6.
Bȯckenhauer, H., Komm, D., Krȧlovic, R., Rossmanith, P.: The online knapsack problem: Advice and randomization. Theor. Comput. Sci. 527, 61–72 (2014)MathSciNetCrossRefMATH
7.
Böckenhauer, H.J., Hromkovic, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theoret. Comput. Sci. 554, 95–108 (2014)MathSciNetCrossRefMATH
8.
Böckenhauer, H.J., Komm, D., Královič, R., Královič, R.: On the advice complexity of the k-server problem. In: Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci., vol. 6755, pp. 207–218. Springer (2011)
9.
Böckenhauer, H.J., Komm, D., Královič, R., Královič, R., Mömke, T.: On the advice complexity of online problems. In: Proc. 20th International Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Comput. Sci., vol. 5878, pp. 331–340. Springer (2009)
10.
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
11.
Boyar, J., Favrholdt, L., Kudahl, C., Larsen, K. S., Mikkelsen, J.W.: Online algorithms with advice: A survey. SIGACT News 47(3), 93–129 (2016)MathSciNetCrossRefMATH
12.
Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: On the list update problem with advice. Inf. Comput. (2016)
13.
14.
Dobrev, S., Kralovic, R., Pardubská, D.: How much information about the future is needed? In: Proc. 34th International Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lecture Notes in Comput. Sci., vol. 4910, pp. 247–258. Springer (2008)
15.
Dobrev, S., Královič, R., Pardubská, D.: Measuring the problem-relevant information in input. RAIRO Inform Theor. Appl. 43(3), 585–613 (2009)MathSciNetCrossRefMATH
16.
Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. Theoret. Comput. Sci. 412(24), 2642–2656 (2011)MathSciNetCrossRefMATH
17.
18.
19.
Gambosi, G., Postiglione, A., Talamo, M.: Algorithms for the relaxed online bin-packing model. SIAM J. Comput. 30(5), 1532–1551 (2000)MathSciNetCrossRefMATH
20.
Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Fischer, P.C., Zeiger, H.P., Ullman, J.D., Rosenberg, A.L. (eds.) STOC, pp 143–150. ACM (1972)
21.
Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing problems - a survey. In: Ausiello, G., Lucertini, M. (eds.) Analysis and Design of Algorithms in Combinatorial Optimization, pp 147–172. Springer, New York (1981)
22.
Grove, E.F.: Online binpacking with lookahead. In: Proc. 6th Symp. on Discrete Algorithms (SODA), pp. 430–436 (1995)
23.
Gupta, S., Kamali, S., López-Ortiz, A.: On advice complexity of the k-server problem under sparse metrics. Theory Comput. Syst. 59(3), 476–499 (2016)MathSciNetCrossRefMATH
24.
Heydrich, S., van Stee, R.: Beating the harmonic lower bound for online bin packing. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 41:1–41:14 (2016)
25.
Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Ph.D. thesis, MIT, Cambridge MA (1973)
26.
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)MathSciNetCrossRefMATH
27.
M., J.W.: Randomization can be as helpful as a glimpse of the future in online computation. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 39:1–39:14 (2016)
28.
29.
30.
Renault, M.P., Rosėn, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. Theor. Comput. Sci. 600, 155–170 (2015)MathSciNetCrossRefMATH
31.
Sloane, N.J.A.: The on-line encyclopedia of integer sequences. Sequence A000041
Metadata
Title
Online Bin Packing with Advice of Small Size
Authors
Spyros Angelopoulos
Christoph Dürr
Shahin Kamali
Marc P. Renault
Adi Rosén
Publication date
12-04-2018
Publisher
Springer US
Published in
Theory of Computing Systems / Issue 8/2018
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-018-9862-5

Other articles of this Issue 8/2018

Theory of Computing Systems 8/2018 Go to the issue

OriginalPaper

Reasoning About XML Constraints Based on XML-to-Relational Mappings

OriginalPaper

Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

OriginalPaper

Primitivity, Uniform Minimality, and State Complexity of Boolean Operations

OriginalPaper

Finger Search in Grammar-Compressed Strings

OriginalPaper

The Most Points Connected-Covering Problem with Two Disks

OriginalPaper

Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks

Premium Partner

    Image Credits