Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

More on ordered open end bin packing

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

We consider the Ordered Open End Bin Packing problem. Items of sizes in (0, 1] are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size is strictly below 1. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below 2, and its value is close to the lower bound. This is in contrast to the best possible absolute competitive ratio, which is equal to 2. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario, we design an asymptotic polynomial time approximation scheme.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Balogh, J., Békési, J., Dósa, G., Epstein, L., Kellerer, H., Levin, A., & Tuza, Z. (2015). Offline black and white bin packing. Theoretical Computer Science, 596, 92–101.

    Article  Google Scholar 

  • Balogh, J., Békési, J., Dósa, G., Epstein, L., Kellerer, H., & Tuza, Z. (2015). Online results for black and white bin packing. Theory of Computer Systems, 56(1), 137–155.

    Article  Google Scholar 

  • Balogh, J., Békési, J., Dósa, G., Epstein, L., & Levin, A. (2018). A new and improved algorithm for online bin packing. In Proceedings of the 26th European symposium on algorithms (ESA2018), pp. 5:1–5:14.

  • Balogh, J., Békési, J., Dósa, G., Epstein, L., & Levin, A. (2019). Lower bounds for several online variants of bin packing. Theory of Computing Systems, 63(8), 1757–1780.

    Article  Google Scholar 

  • Balogh, J., Békési, J., Dósa, G., Epstein, L., & Levin, A. (2021). A new lower bound for classic online bin packing. Algorithmica, 83(7), 2047–2062.

    Article  Google Scholar 

  • Balogh, J., Békési, J., Dósa, G., Sgall, J., & van Stee, R. (2019). The optimal absolute ratio for online bin packing. Journal of Computer and System Sciences, 102, 1–17.

    Article  Google Scholar 

  • Balogh, J., Békési, J., & Galambos, G. (2012). New lower bounds for certain classes of bin packing algorithms. Theoretical Computer Science, 440, 1–13.

    Article  Google Scholar 

  • Békési, J., Dósa, G., & Epstein, L. (2016). Bounds for online bin packing with cardinality constraints. Information and Computation, 249, 190–204.

    Article  Google Scholar 

  • Berndt, S., Jansen, K., & Klein, K.-M. (2020). Fully dynamic bin packing revisited. Mathematical Programming, 179(1), 109–155.

    Article  Google Scholar 

  • Böhm, M., Dósa, G., Epstein, L., Sgall, J., & Veselý, P. (2018). Colored bin packing: Online algorithms and lower bounds. Algorithmica, 80(1), 155–184.

    Article  Google Scholar 

  • Chrobak, M., Sgall, J., & Woeginger, G. J. (2011). Two-bounded-space bin packing revisited. In Proceedings of the 19th Annual European symposium on algorithms (ESA2011), pp. 263–274.

  • Dosa, G., Tuza, Z., & Ye, D. (2013). Bin packing with “largest in bottom’’ constraint: Tighter bounds and generalizations. Journal of Combinatorial Optimization, 26(3), 416–436.

    Article  Google Scholar 

  • Epstein, L. (2009). On online bin packing with LIB constraints. Naval Research Logistics, 56(8), 780–786.

    Article  Google Scholar 

  • Epstein, L. (2019). A lower bound for online rectangle packing. Journal of Combinatorial Optimization, 38(3), 846–866.

    Article  Google Scholar 

  • Epstein, L., & Levin, A. (2008). Asymptotic fully polynomial approximation schemes for variants of open-end bin packing. Information Processing Letters, 109(1), 32–37.

    Article  Google Scholar 

  • Epstein, L., & Levin, A. (2020). A note on a variant of the online open end bin packing problem. Operations Research Letters, 48(6), 844–849.

    Article  Google Scholar 

  • Fernandez de la Vega, W., & Lueker, G. S. (1981). Bin packing can be solved within \(1+\varepsilon \) in linear time. Combinatorica, 1(4), 349–355.

    Article  Google Scholar 

  • Finlay, L., & Manyem, P. (2005). Online LIB problems: Heuristics for bin covering and lower bounds for bin packing. RAIRO Operetions Research, 39(3), 163–183.

    Article  Google Scholar 

  • Gai, L., & Zhang, G. (2009). Hardness of lazy packing and covering. Operations Research Letters, 37(2), 89–92.

    Article  Google Scholar 

  • Kannan, R. (1983). Improved algorithms for integer programming and related lattice problems. In Proceedings of the 15th annual ACM symposium on theory of computing (STOC1983), pp. 193–206.

  • Karmarkar, N., & Karp, R. M. (1982). An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd annual symposium on foundations of computer science (FOCS1982), pp. 312–320.

  • Lee, C. C., & Lee, D. T. (1985). A simple online bin packing algorithm. Journal of the ACM, 32(3), 562–572.

    Article  Google Scholar 

  • Lenstra, H. W., Jr. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538–548.

    Article  Google Scholar 

  • Leung, J.Y.-T., Dror, M., & Young, G. H. (2001). A note on an open-end bin packing problem. Journal of Scheduling, 4(4), 201–207.

    Article  Google Scholar 

  • Lin, M., Yang, Y., & Xu, J. (2010). Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems. Algorithmica, 57(2), 232–251.

    Article  Google Scholar 

  • Lin, M., Yang, Y., & Xu, J. (2010). On lazy bin covering and packing problems. Theoretical Computer Science, 411(1), 277–284.

    Article  Google Scholar 

  • Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989). Online bin packing in linear time. Journal of Algorithms, 10, 305–326.

    Article  Google Scholar 

  • van Vliet, A. (1992). An improved lower bound for online bin packing algorithms. Information Processing Letters, 43(5), 277–284.

  • Yang, J., & Leung, J. Y. (2003). The ordered open-end bin packing problem. Operations Research, 51(5), 759–770.

    Article  Google Scholar 

  • Zhang, G. (1998). Parameterized on-line open-end bin packing. Computing, 60(3), 267–274.

    Article  Google Scholar 

  • Zhang, G. (2002). Private communication

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, University of Szeged, Szeged, Hungary

    János Balogh

  2. Department of Mathematics, University of Haifa, Haifa, Israel

    Leah Epstein

  3. Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel

    Asaf Levin

Authors
  1. János Balogh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leah Epstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Asaf Levin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Leah Epstein.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

J. Balogh: This research was supported by the projects “Extending the activities of the HU-MATHS-IN Hungarian Industrial and Innovation Mathematical Service Network” EFOP-3.6.2-16-2017-00015, and the project “Integrated program for training new generation of scientists in the fields of computer science” EFOP-3.6.3-VEKOP-16-2017-00002, supported by the European Union and co-funded by the European Social Fund. A. Levin: Partially supported by grant number 308/18 of ISF - Israeli Science Foundation.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Balogh, J., Epstein, L. & Levin, A. More on ordered open end bin packing. J Sched 24, 589–614 (2021). https://doi.org/10.1007/s10951-021-00709-3

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-021-00709-3

Keywords

Search

Navigation