The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
상자 포장 문제에서는 크기가 1에서 2 사이인 주어진 항목을 용량 1의 상자에 넣어야 합니다. 목표는 하나 이상의 항목이 포함된 저장소 수를 최소화하는 것입니다. 빈 포장 문제에 대한 온라인 알고리즘은 각 품목이 도착할 때 하나씩 배치할 위치를 결정합니다. 빈 패킹 문제의 점근적 근사 비율은 문제에 대한 최적의 온라인 알고리즘의 성능으로 정의됩니다. 이 값은 빈 포장 문제의 본질적인 경도를 나타냅니다. 본 논문에서는 모든 품목의 크기가 α 또는 β(≤ α)인 빈 포장 문제를 연구합니다. $alpha > rac{2}{1}$에 대한 점근 근사 비율은 이미 식별되었지만 $alpha leq rac{2}{XNUMX}$에 대한 점근 근사 비율은 부분적으로만 알려져 있습니다. 이 논문은 선형 최적화 문제를 공식화하여 모든 $alpha leq rac{XNUMX}{XNUMX}$에 대한 점근 근사 비율의 하한을 제공하는 최초의 논문입니다. 또한, 이중 실현 가능한 솔루션을 구성하여 닫힌 형태의 또 다른 하한을 도출합니다.
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.
부
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
부
@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},}
부
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 -