Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Online Bin Packing with Advice

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the online bin packing problem under the advice complexity model where the “online constraint” is relaxed and an algorithm receives partial information about the future items. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with\(\log n + o(\log n)\) bits of advice, achieves a competitive ratio of\(3/2\) for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives\(2n + o(n)\) bits of advice and achieves a competitive ratio of\(4/3 + \varepsilon \). Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1

Similar content being viewed by others

References

  1. Albers, S., Hellwig, M.: Semi-online scheduling revisited. Theor. Comput. Sci.443, 1–9 (2012)

    Article MATH MathSciNet  Google Scholar 

  2. Ásgeirsson, E.I., Ayesta, U., Coffman, E.G., Etra, J., Momcilovic, P., Phillips, D.J., Vokhshoori, V., Wang, Z., Wolfe, J.: Closed on-line bin packing. Acta Cybern.15(3), 361–367 (2002)

    MATH  Google Scholar 

  3. Balogh, J., Békési, J.: Semi-on-line bin packing: a short overview and a new lower bound. Cent. Eur. J. Oper. Res.21(4), 685–698 (2013)

    Article MathSciNet  Google Scholar 

  4. 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)

    Article  Google Scholar 

  5. Bianchi, M.P., Böckenhauer, H., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica70(1), 92–111 (2014)

    Article MATH MathSciNet  Google Scholar 

  6. Bianchi, M.P., Böckenhauer, H.J., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Proc. 18th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7434, pp. 519–530. Springer, Berlin (2012)

  7. Bianchi, M.P., Böckenhauer, H.J., Hromkovic, J., Krug, S., Steffen, B.: On the advice complexity of the online\(L(2, 1)\)-coloring problem on paths and cycles. In: Du, D., Zhang G. (eds.) Proc. 19th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7936, pp. 53–64. Springer, Berlin (2013)

  8. Błażewicz, J., Ecker, K.: A linear time algorithm for restricted bin packing and scheduling problems. Oper. Res. Lett.2(2), 80–83 (1983)

    Article MATH MathSciNet  Google Scholar 

  9. Böckenhauer, H., Komm, D., Královic, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci.527, 61–72 (2014)

    Article MATH  Google Scholar 

  10. 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. In: Du, D., Zhang, G. (eds.) Proc. 19th Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science, vol. 7936, pp. 493–505. Springer, Berlin (2013)

  11. Böckenhauer, H.J., Komm, D., Královič, R., Královič, R.: On the advice complexity of the\(k\)-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Proc. 38th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, vol. 6755, pp. 207–218. Springer, Berlin (2011)

  12. Böckenhauer, H.J., Komm, D., Královič, R., Královič, R., Mömke, T.: On the advice complexity of online problems. In: Dong, Y., Du, D., Ibarra, O.H. (eds.) Proc. 20th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 5878, pp. 331–340. Springer, Berlin (2009)

  13. Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: On the list update problem with advice. In: Dediu, A.H., Martín-Vide, C., Sierra-Rodríguez, J.L., Truthe, B. (eds.) Proc. 8th International Conference on Language and Automata Theory and Applications (LATA), pp. 210–221 (2014)

  14. Cheng, T.C.E., Kellerer, H., Kotov, V.: Semi-on-line multiprocessor scheduling with given total processing time. Theor. Comput. Sci.337(1–3), 134–146 (2005)

    Article MATH MathSciNet  Google Scholar 

  15. Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Co, Boston (1997)

    Google Scholar 

  16. Coffman Jr, E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 455–531. Springer, New York (2013)

    Chapter  Google Scholar 

  17. de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1 +\(\epsilon \) in linear time. Combinatorica1, 349–355 (1981)

    Article MATH MathSciNet  Google Scholar 

  18. Dobrev, S., Královic, R., Markou, E.: Online graph exploration with advice. In: Even, G., Halldórsson, M.M. (eds.) Proc. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 7355, pp. 267–278. Springer, Berlin (2012)

  19. Dobrev, S., Královič, R., Pardubská, D.: Measuring the problem-relevant information in input. RAIRO Theor. Inform. Appl.43(3), 585–613 (2009)

    Article MATH  Google Scholar 

  20. Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. Theor. Comput. Sci.412(24), 2642–2656 (2011)

    Article MATH  Google Scholar 

  21. Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optim.19(3), 1270–1298 (2008)

    Article MATH MathSciNet  Google Scholar 

  22. Forišek, M., Keller, L., Steinová, M.: Advice complexity of online coloring for paths. In: Dediu, A.H., Martín-Vide, C. (eds.) Proc. 6th International Conference on Language and Automata Theory and Applications (LATA), Lecture Notes in Computer Science, vol. 7183, pp. 228–239. Springer, Berlin (2012)

  23. Galambos, G., Woeginger, G.J.: Repacking helps in bounded space online bin packing. Computing49, 329–338 (1993)

    Article MATH MathSciNet  Google Scholar 

  24. Gambosi, G., Postiglione, A., Talamo, M.: Algorithms for the relaxed online bin-packing model. SIAM J. Comput.30(5), 1532–1551 (2000)

    Article MATH MathSciNet  Google Scholar 

  25. Goemans, M.X., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: Chekuri, C. (ed.) Proc. 25th Symposium on Discrete Algorithms (SODA), pp. 830–839 (2014)

  26. Grove, E.F.: Online binpacking with lookahead. In: Clarkson, K.L. (ed.) Proc. 6th Symposium on Discrete Algorithms (SODA), pp. 430–436 (1995)

  27. Hromkovič, J., Královič, R., Královič, R.: Information complexity of online problems. In: Hlinený, P., Kucera, A. (eds.) Proc. 35th Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 6281, pp. 24–36. Springer, Berlin (2010)

  28. Ivkovic, Z., Lloyd, E.: A fundamental restriction on fully dynamic maintenance of bin packing. Inf. Process. Lett.59, 229–232 (1996)

    Article MATH MathSciNet  Google Scholar 

  29. Komm, D., Královic, R., Mömke, T.: On the advice complexity of the set cover problem. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds.) Proc. 7th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science, vol. 7353, pp. 241–252. Springer, Berlin (2012)

  30. Komm, D., Královič, R.: Advice complexity and barely random algorithms. RAIRO Theor. Inform. Appl.45(2), 249–267 (2011)

    Article MATH MathSciNet  Google Scholar 

  31. Renault, M.P., Rosén, A.: On online algorithms with advice for the\(k\)-server problem. In: Solis-Oba, R., Persiano, G. (eds.) Proc. 9th International Workshop in Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, vol. 7164, pp. 198–210. Springer, Berlin (2011)

  32. Renault, M.P., Rosén, A., van Stee, R.: Online algorithms with advice for bin packing and scheduling problems. CoRR abs/1311.7589 (2013)

  33. Seibert, S., Sprock, A., Unger, W.: Advice complexity of the online coloring problem. In: Spirakis, P.G., Serna, M.J. (eds.) Proc. 8th International Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science, vol. 7878, pp. 345–357. Springer, Berlin (2013)

  34. Seiden, S.S.: On the online bin packing problem. J. ACM49, 640–671 (2002)

    Article MathSciNet  Google Scholar 

  35. Tan, Z., Zhang, A.: Online and semi-online scheduling. In: Pardalos, P.M. (ed.) Handbook of Combinatorial Optimization, pp. 2191–2252. Springer, Berlin (2013)

    Chapter  Google Scholar 

  36. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

    Joan Boyar & Kim S. Larsen

  2. David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada

    Shahin Kamali & Alejandro López-Ortiz

Authors
  1. Joan Boyar

    You can also search for this author inPubMed Google Scholar

  2. Shahin Kamali

    You can also search for this author inPubMed Google Scholar

  3. Kim S. Larsen

    You can also search for this author inPubMed Google Scholar

  4. Alejandro López-Ortiz

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toKim S. Larsen.

Additional information

The work of the first and third author was partially supported by the Danish Council for Independent Research, Natural Sciences, and the Villum Foundation, and most of the work was carried out while these authors were visiting the University of Waterloo.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boyar, J., Kamali, S., Larsen, K.S.et al. Online Bin Packing with Advice.Algorithmica74, 507–527 (2016). https://doi.org/10.1007/s00453-014-9955-8

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp