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

Hiroshi Fujiwara () and Koji Kobayashi ()
Additional contact information
Hiroshi Fujiwara: Toyohashi University of Technology
Koji Kobayashi: National Institute of Informatics

Journal of Combinatorial Optimization, 2015, vol. 29, issue 1, No 5, 67-87

Abstract: Abstract The bin packing problem has been extensively studied and numerous variants have been considered. The $$k$$ 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$$ 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$$ 2 ≈ 1.41421 and $$1.5$$ 1.5 on the asymptotic competitive ratio for $$k=2$$ k = 2 and $$3$$ 3 , respectively. For $$k \ge 4$$ k ≥ 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$$ k -item bin packing problem. First, we improve the previous lower bound $$1.41421$$ 1.41421 to $$1.42764$$ 1.42764 for $$k=2$$ k = 2 . Moreover, we propose a new method to derive lower bounds for general $$k$$ k and present improved bounds for various cases of $$k \ge 4$$ k ≥ 4 . For example, we improve $$1.33333$$ 1.33333 to $$1.5$$ 1.5 for $$k = 4$$ k = 4 , and $$1.33333$$ 1.33333 to $$1.47058$$ 1.47058 for $$k = 5$$ k = 5 .

Keywords: Bin packing problem; Online algorithm; Competitive analysis; Cardinality constraint (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9679-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:1:d:10.1007_s10878-013-9679-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9679-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().