Online Bin Packing with Cardinality Constraints Resolved

Authors Janos Balogh, Jozsef Bekesi, Gyorgy Dosa, Leah Epstein, Asaf Levin



PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.10.pdf
  • Filesize: 441 kB
  • 14 pages

Document Identifiers

Author Details

Janos Balogh
Jozsef Bekesi
Gyorgy Dosa
Leah Epstein
Asaf Levin

Cite AsGet BibTex

Janos Balogh, Jozsef Bekesi, Gyorgy Dosa, Leah Epstein, and Asaf Levin. Online Bin Packing with Cardinality Constraints Resolved. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.10

Abstract

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k >= 2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.
Keywords
  • Online algorithms
  • bin packing
  • cardinality constraints
  • lower bounds

Metrics

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

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, and G. Galambos. New lower bounds for certain bin packing algorithms. Theoretical Computer Science, 1:1-13, 2012. Google Scholar
  6. J. Békési, Gy. Dósa, and L. Epstein. Bounds for online bin packing with cardinality constraints. Information and Computation, 249:190-204, 2016. Google Scholar
  7. David 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
  8. David Blitz, Andre van Vliet, and Gerhard J. Woeginger. Lower bounds on the asymptotic worst-case ratio of online bin packing algorithms. Unpublished manuscript, 1996. Google Scholar
  9. A. Caprara, H. Kellerer, and U. Pferschy. Approximation schemes for ordered vector packing problems. Naval Research Logistics, 92:58-69, 2003. Google Scholar
  10. L. Epstein. Online bin packing with cardinality constraints. SIAM Journal on Discrete Mathematics, 20(4):1015-1030, 2006. Google Scholar
  11. 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
  12. H. Fujiwara and K. M. Kobayashi. Improved lower bounds for the online bin packing problem with cardinality constraints. Journal of Combinatorial Optimization, 29(1):67-87, 2015. Google Scholar
  13. G. Galambos, H. Kellerer, and G. J. Woeginger. A lower bound for online vector packing algorithms. Acta Cybernetica, 10:23-34, 1994. Google Scholar
  14. M. R. Garey, R. L. Graham, D. S. Johnson, and A. C. C. Yao. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory Series A, 21(3):257-298, 1976. Google Scholar
  15. K. Jansen, M. Maack, and M. Rau. Approximation schemes for machine scheduling with resource (in-)dependent processing times. In Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA'16), pages 1526-1542, 2016. 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. H. Kellerer and U. Pferschy. Cardinality constrained bin-packing problems. Annals of Operations Research, 92:335-348, 1999. Google Scholar
  18. K. L. Krause, V. Y. Shen, and H. D. Schwetman. Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. Journal of the ACM, 22(4):522-550, 1975. Google Scholar
  19. K. L. Krause, V. Y. Shen, and H. D. Schwetman. Errata: "Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems". Journal of the ACM, 24(3):527-527, 1977. Google Scholar
  20. C. C. Lee and D. T. Lee. A simple online bin packing algorithm. Journal of the ACM, 32(3):562-572, 1985. Google Scholar
  21. 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
  22. S. S. Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640-671, 2002. Google Scholar
  23. A. van Vliet. An improved lower bound for online bin packing algorithms. Information Processing Letters, 43(5):277-284, 1992. Google Scholar
  24. A. C. C. Yao. New algorithms for bin packing. Journal of the ACM, 27:207-227, 1980. 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