[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Improved lower bounds for the online bin packing problem with cardinality constraints

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

The bin packing problem has been extensively studied and numerous variants have been considered. The \(k\)-item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522–550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most \(k\). For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143:238–251, 2004) provided lower bounds \(\sqrt{2} \approx 1.41421\) and \(1.5\) on the asymptotic competitive ratio for \(k=2\) and \(3\), respectively. For \(k \ge 4\), some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277–284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online \(k\)-item bin packing problem. First, we improve the previous lower bound \(1.41421\) to \(1.42764\) for \(k=2\). Moreover, we propose a new method to derive lower bounds for general \(k\) and present improved bounds for various cases of \(k \ge 4\). For example, we improve \(1.33333\) to \(1.5\) for \(k = 4\), and \(1.33333\) to \(1.47058\) for \(k = 5\).

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Balogh J, Békési J, Galambos G (2012) New lower bounds for certain classes of bin packing algorithms. Theor Comput Sci 440–441:1–13

    Article  Google Scholar 

  • Babel L, Chen B, Kellerer H, Kotov V (2004) Algorithms for on-line bin-packing problems with cardinality constraints. Discret Appl Math 143(1–3):238–251

    Article  MATH  MathSciNet  Google Scholar 

  • Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  • Caprara A, Kellerer H, Pferschy U (2003) Approximation schemes for ordered vector packing problems. Naval Res Logist 50(1):58–69

    Article  MATH  MathSciNet  Google Scholar 

  • Epstein L, Levin A (2010) AFPTAS results for common variants of bin packing: a new method for handling the small items. SIAM J Optim 20(6):3121–3145

    Article  MATH  MathSciNet  Google Scholar 

  • Epstein L (2006) Online bin packing with cardinality constraints. SIAM J Discret Math 20(4):1015–1030

    Article  MATH  Google Scholar 

  • Kellerer H, Pferschy U (1999) Cardinality constrained bin-packing problems. Ann Oper Res 92:335–348

    Article  MATH  MathSciNet  Google Scholar 

  • Krause KL, Shen VY, Schwetman HD (1975) Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J ACM 22(4):522–550

    Article  MATH  MathSciNet  Google Scholar 

  • Krause KL, Shen VY, Schwetman HD (1977) Errata: “analysis of several task-scheduling algorithms for a model of multiprogramming computer systems”. J ACM 24(3):527

    Article  MathSciNet  Google Scholar 

  • Ramanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10(3):305–326

    Article  MATH  MathSciNet  Google Scholar 

  • Seiden SS (2002) On the online bin packing problem. J ACM 49(5):640–671

    Article  MathSciNet  Google Scholar 

  • Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202–208

    Article  MathSciNet  Google Scholar 

  • van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Inf Process Lett 43(5):277–284

    Article  MATH  Google Scholar 

  • Yao AC (1980) New algorithms for bin packing. J ACM 27(2):207–227

    Article  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported by KAKENHI (23700014 and 23500014).

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Toyohashi University of Technology, 1-1 Tenpaku-cho, Toyohashi, 441-8580, Japan

    Hiroshi Fujiwara

  2. Principles of Informatics Research Division, National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

    Koji Kobayashi

Authors
  1. Hiroshi Fujiwara
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Koji Kobayashi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hiroshi Fujiwara.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fujiwara, H., Kobayashi, K. Improved lower bounds for the online bin packing problem with cardinality constraints. J Comb Optim 29, 67–87 (2015). https://doi.org/10.1007/s10878-013-9679-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-013-9679-8

Keywords

Search

Navigation