Document Open Access Logo

A New and Improved Algorithm for Online Bin Packing

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.5.pdf
  • Filesize: 327 kB
  • 14 pages

Document Identifiers

Author Details

János Balogh
  • Department of Applied Informatics, Gyula Juhász Faculty of Education, University of Szeged, Hungary.
József Békési
  • Department of Applied Informatics, Gyula Juhász Faculty of Education, University of Szeged, Hungary.
György Dósa
  • Department of Mathematics, University of Pannonia, Veszprém, Hungary.
Leah Epstein
  • Department of Mathematics, University of Haifa, Haifa, Israel.
Asaf Levin
  • Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel.

Cite As Get BibTex

János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A New and Improved Algorithm for Online Bin Packing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.5

Abstract

We revisit the classic online bin packing problem studied in the half-century. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called bins of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier by providing an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.57829.
Our main contribution is the introduction of the simple analysis based on weight function to analyze the state of the art online algorithms for the classic online bin packing problem. The previously used analytic tool named weight system was too complicated for the community in this area to adjust it for other problems and other algorithmic tools that are needed in order to improve the current best algorithms. We show that the weight system based analysis is not needed for the analysis of the current algorithms for the classic online bin packing problem. The importance of a simple analysis is demonstrated by analyzing several new features together with all existing techniques, and by proving a better competitive ratio than the previously best one.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Bin packing
  • online algorithms
  • competitive analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. L. Babel, B. Chen, H. Kellerer, and V. Kotov. Algorithms for on-line bin-packing problems with cardinality constraints. Discrete Applied Mathematics, 143(1-3):238-251, 2004. Google Scholar
  2. B. S. Baker and E. G. Coffman, Jr. A tight asymptotic bound for next-fit-decreasing bin-packing. SIAM J. on Algebraic and Discrete Methods, 2(2):147-152, 1981. Google Scholar
  3. J. Balogh, J. Békési, Gy. Dósa, J. Sgall, and R. van Stee. The optimal absolute ratio for online bin packing. In Proc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2015), pages 1425-1438, 2015. Google Scholar
  4. J. Balogh, J. Békési, and G. Galambos. New lower bounds for certain bin packing algorithms. Theoretical Computer Science, 1:1-13, 2012. Google Scholar
  5. E. G. Coffman, M. R. Garey, and D. S. Johnson. Approximation algorithms for bin packing: A survey. In D. Hochbaum, editor, Approximation algorithms. PWS Publishing Company, 1997. Google Scholar
  6. J. Csirik and G. J. Woeginger. On-line packing and covering problems. In A. Fiat and G. J. Woeginger, editors, Online Algorithms: The State of the Art, pages 147-177, 1998. Google Scholar
  7. Gy. Dósa and J. Sgall. First Fit bin packing: A tight analysis. In Proc. of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS2013), pages 538-549, 2013. Google Scholar
  8. Gy. Dósa and J. Sgall. Optimal analysis of Best Fit bin packing. In The 41st International Colloquium on Automata, Languages and Programming (ICALP2014), pages 429-441, 2014. Google Scholar
  9. L. Epstein and A. Levin. A robust APTAS for the classical bin packing problem. Mathematical Programming, 119(1):33-49, 2009. Google Scholar
  10. W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  11. S. Heydrich and R. van Stee. Beating the harmonic lower bound for online bin packing. In Proc. of 43rd International Colloquium on Automata, Languages, and Programming (ICALP2016), pages 41:1-41:14, 2016. Google Scholar
  12. R. Hoberg and T. Rothvoss. A logarithmic additive integrality gap for bin packing. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2017), pages 2616-2625, 2017. Google Scholar
  13. K. Jansen and K.-M. Klein. A robust AFPTAS for online bin packing with polynomial migration. In Proc. of the 40th International Colloquium on Automata, Languages, and Programming (ICALP2013), part I, pages 589-600, 2013. Google Scholar
  14. D. S. Johnson. Near-optimal bin packing algorithms. PhD thesis, MIT, Cambridge, MA, 1973. Google Scholar
  15. D. S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8:272-314, 1974. Google Scholar
  16. D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3:256-278, 1974. Google Scholar
  17. N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proc. of the 23rd Annual Symposium on Foundations of Computer Science (FOCS'82), pages 312-320, 1982. Google Scholar
  18. C. C. Lee and D. T. Lee. A simple online bin packing algorithm. Journal of the ACM, 32(3):562-572, 1985. Google Scholar
  19. P. Ramanan, D. J. Brown, C. C. Lee, and D. T. Lee. Online bin packing in linear time. Journal of Algorithms, 10:305-326, 1989. Google Scholar
  20. M. B. Richey. Improved bounds for harmonic-based bin packing algorithms. Discrete Applied Mathematics, 34(1-3):203-227, 1991. Google Scholar
  21. T. Rothvoss. Better bin packing approximations via discrepancy theory. SIAM Journal on Computing, 45(3):930-946, 2016. Google Scholar
  22. R. van Stee S. Heydrich. Beating the harmonic lower bound for online bin packing. The Computing Res. Rep. (CoRR), abs/1707.01728, 2017. URL: http://arxiv.org/abs/1511.00876v3.
  23. S. S. Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640-671, 2002. Google Scholar
  24. D. Simchi-Levi. New worst-case results for the bin-packing problem. Naval Research Logistics, 41(4):579-585, 1994. Google Scholar
  25. J. D. Ullman. The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971. Google Scholar
  26. A. van Vliet. An improved lower bound for online bin packing algorithms. Information Processing Letters, 43(5):277-284, 1992. Google Scholar
  27. A. C. C. Yao. New algorithms for bin packing. Journal of the ACM, 27:207-227, 1980. Google Scholar
  28. G. Zhang. Private communication. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact