The search functionality is under construction.

The search functionality is under construction.

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

Hiroshi FUJIWARA

Shinshu University

Ken ENDO

Shinshu University

Hiroaki YAMAMOTO

Shinshu University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hiroshi FUJIWARA, Ken ENDO, Hiroaki YAMAMOTO, "Analysis of Lower Bounds for Online Bin Packing with Two Item Sizes" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1127-1133, September 2021, doi: 10.1587/transfun.2020DMP0007.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0007/_p

Copy

@ARTICLE{e104-a_9_1127,

author={Hiroshi FUJIWARA, Ken ENDO, Hiroaki YAMAMOTO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Analysis of Lower Bounds for Online Bin Packing with Two Item Sizes},

year={2021},

volume={E104-A},

number={9},

pages={1127-1133},

abstract={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.},

keywords={},

doi={10.1587/transfun.2020DMP0007},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1127

EP - 1133

AU - Hiroshi FUJIWARA

AU - Ken ENDO

AU - Hiroaki YAMAMOTO

PY - 2021

DO - 10.1587/transfun.2020DMP0007

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E104-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2021

AB - 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.

ER -