Document Open Access Logo

Truly Asymptotic Lower Bounds for Online Vector Bin Packing

Authors János Balogh, Ilan Reuven Cohen, Leah Epstein, Asaf Levin

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.8.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Author Details

János Balogh
  • Institute of Informatics, University of Szeged, Hungary
Ilan Reuven Cohen
  • Faculty of Engineering, Bar-Ilan University, Ramat-Gan, Israel
Leah Epstein
  • Department of Mathematics, University of Haifa, Israel
Asaf Levin
  • Faculty of Industrial Engineering and Management, Technion, Haifa, Israel

Funding

The research of J. Balogh was supported by the project "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. The research of A. Levin was partially supported by ISF - Israeli Science Foundation grant number 308/18.

Acknowledgements

The results of this paper are based on the arxiv versions [J. Balogh et al., 2020; L. Babel et al., 2004]. Part of the work in [L. Babel et al., 2004] has been done while Ilan Reuven Cohen was a postdoctoral fellow at CWI Amsterdam and TU Eindhoven, he would like to thank Nikhil Bansal for discussions and suggestions related to fractional coloring and ideas from [L. Lov{á}sz, 1975].

Cite AsGet BibTex

János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin. Truly Asymptotic Lower Bounds for Online Vector Bin Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.8

Abstract

In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d ≥ 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of Ω(√d). Our main result is that the lower bound of Ω(d/log² d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Mathematics of computing
Keywords
  • Bin packing
  • online algorithms
  • approximation algorithms
  • vector packing

Metrics

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

Related Versions

References

  1. Y. Azar, I. R. Cohen, A. Fiat, and A. Roytman. Packing small vectors. In Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA'16), pages 1511-1525, 2016. Google Scholar
  2. Y. Azar, I. R. Cohen, S. Kamara, and F. B. Shepherd. Tight bounds for online vector bin packing. In Proc. of the 45th ACM Symposium on Theory of Computing (STOC'13), pages 961-970, 2013. Google Scholar
  3. Y. Azar, I. R. Cohen, and A. Roytman. Online lower bounds via duality. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA'17), pages 1038-1050, 2017. Google Scholar
  4. 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
  5. J. Balogh, J. Békési, Gy. Dósa, L. Epstein, and A. Levin. A new and improved algorithm for online bin packing. In Proc. of the 26th European Symposium on Algorithms (ESA'18), pages 5:1-5:14, 2018. Google Scholar
  6. J. Balogh, J. Békési, Gy. Dósa, L. Epstein, and A. Levin. Online bin packing with cardinality constraints resolved. Journal of Computer and System Sciences, 112:34-49, 2020. Google Scholar
  7. J. Balogh, J. Békési, Gy. Dósa, L. Epstein, and A. Levin. A new lower bound for classic online bin packing. Algorithmica, 83(7):2047-2062, 2021. Google Scholar
  8. J. Balogh, J. Békési, Gy. Dósa, J. Sgall, and R. van Stee. The optimal absolute ratio for online bin packing. Journal of Computer and System Sciences, 102:1-17, 2019. Google Scholar
  9. J. Balogh, L. Epstein, and A. Levin. Truly asymptotic lower bounds for online vector bin packing. CoRR, abs/2008.00811, 2020. URL: http://arxiv.org/abs/2008.00811.
  10. N. Bansal, A. Caprara, and M. Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4):1256-1278, 2009. Google Scholar
  11. N. Bansal and I. R. Cohen. An asymptotic lower bound for online vector bin packing. CoRR, abs/2007.15709, 2020. URL: http://arxiv.org/abs/2007.15709.
  12. N. Bansal, M. Eliás, and A. Khan. Improved approximation for vector bin packing. In Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA'16), pages 1561-1579, 2016. Google Scholar
  13. D. Blitz. Lower bounds on the asymptotic worst-case ratios of on-line bin packing algorithms. Technical Report 114682, University of Rotterdam, 1996. M.Sc. thesis. Google Scholar
  14. D. Blitz, A. van Vliet, and G. J. Woeginger. Lower bounds on the asymptotic worst-case ratio of online bin packing algorithms. Unpublished manuscript, 1996. Google Scholar
  15. A. Caprara, H. Kellerer, and U. Pferschy. Approximation schemes for ordered vector packing problems. Naval Research Logistics, 92:58-69, 2003. Google Scholar
  16. C. Chekuri and S. Khanna. On multidimensional packing problems. SIAM Journal on Computing, 33(4):837-851, 2004. Google Scholar
  17. L. Epstein. Online bin packing with cardinality constraints. SIAM Journal on Discrete Mathematics, 20(4):1015-1030, 2006. Google Scholar
  18. L. Epstein and A. Levin. AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM Journal on Optimization, 20(6):3121-3145, 2010. Google Scholar
  19. 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
  20. G. Galambos, H. Kellerer, and G. J. Woeginger. A lower bound for online vector packing algorithms. Acta Cybernetica, 10:23-34, 1994. Google Scholar
  21. M. R. Garey, R. L. Graham, and D. S. Johnson. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory Series A, 21(3):257-298, 1976. Google Scholar
  22. M. M. Halldórsson and M. Szegedy. Lower bounds for on-line graph coloring. Theoretical Computer Science, 130(1):163-174, 1994. Google Scholar
  23. D. S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8:272-314, 1974. Google Scholar
  24. 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
  25. N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS'82), pages 312-320, 1982. Google Scholar
  26. L. T. Kou and G. Markowsky. Multidimensional bin packing algorithms. IBM Journal of Research and Development, 21(5):443-448, 1977. URL: https://doi.org/10.1147/rd.215.0443.
  27. L. Lovász. On the ratio of optimal integral and fractional covers. Discrete mathematics, 13(4):383-390, 1975. Google Scholar
  28. S. Sandeep. Almost optimal inapproximability of multidimensional packing problems. CoRR, abs/2101.02854, 2021. URL: http://arxiv.org/abs/2101.02854.
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 Imprint Privacy Contact