The search functionality is under construction.
The search functionality is under construction.

Analysis of Lower Bounds for Online Bin Packing with Two Item Sizes

Hiroshi FUJIWARA, Ken ENDO, Hiroaki YAMAMOTO

  • Full Text Views

    0

  • Cite this

Summary :

In the bin packing problem, we are asked to place given items, each being of size between zero and one, into bins of capacity one. The goal is to minimize the number of bins that contain at least one item. An online algorithm for the bin packing problem decides where to place each item one by one when it arrives. The asymptotic approximation ratio of the bin packing problem is defined as the performance of an optimal online algorithm for the problem. That value indicates the intrinsic hardness of the bin packing problem. In this paper we study the bin packing problem in which every item is of either size α or size β (≤ α). While the asymptotic approximation ratio for $alpha > rac{1}{2}$ was already identified, that for $alpha leq rac{1}{2}$ is only partially known. This paper is the first to give a lower bound on the asymptotic approximation ratio for any $alpha leq rac{1}{2}$, by formulating linear optimization problems. Furthermore, we derive another lower bound in a closed form by constructing dual feasible solutions.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1127-1133
Publication Date
2021/09/01
Publicized
2021/03/09
Online ISSN
1745-1337
DOI
10.1587/transfun.2020DMP0007
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category
Algorithms and Data Structures

Authors

Hiroshi FUJIWARA
  Shinshu University
Ken ENDO
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

Keyword