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
Masalah pembungkusan tong sampah ialah masalah mencari penugasan urutan item kepada bilangan minimum tong, setiap satu kapasiti. Algoritma dalam talian untuk masalah pembungkusan tong ialah algoritma yang menetapkan setiap item satu demi satu daripada kepala urutan secara tidak boleh ditarik balik. Gutin, Jensen, dan Yeo (2006) menganggap versi di mana semua item hanya mempunyai dua saiz yang berbeza dan algoritma dalam talian mengetahui dua saiz yang mungkin lebih awal, dan memberikan algoritma dalam talian yang optimum untuk kes apabila saiz yang lebih besar melebihi 1/ 2. Dalam makalah ini kami menyediakan algoritma dalam talian yang optimum untuk beberapa kes apabila saiz yang lebih besar adalah paling banyak 1/2, berdasarkan rangka kerja yang memudahkan reka bentuk dan analisis algoritma.
Hiroshi FUJIWARA
Shinshu University
Masaya KAWAGUCHI
Saitama University
Daiki TAKIZAWA
East Japan Railway Company
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.
Salinan
Hiroshi FUJIWARA, Masaya KAWAGUCHI, Daiki TAKIZAWA, Hiroaki YAMAMOTO, "Optimal Online Bin Packing Algorithms for Some Cases with Two Item Sizes" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1100-1110, September 2023, doi: 10.1587/transfun.2022DMP0008.
Abstract: The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DMP0008/_p
Salinan
@ARTICLE{e106-a_9_1100,
author={Hiroshi FUJIWARA, Masaya KAWAGUCHI, Daiki TAKIZAWA, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Online Bin Packing Algorithms for Some Cases with Two Item Sizes},
year={2023},
volume={E106-A},
number={9},
pages={1100-1110},
abstract={The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.},
keywords={},
doi={10.1587/transfun.2022DMP0008},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - Optimal Online Bin Packing Algorithms for Some Cases with Two Item Sizes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1100
EP - 1110
AU - Hiroshi FUJIWARA
AU - Masaya KAWAGUCHI
AU - Daiki TAKIZAWA
AU - Hiroaki YAMAMOTO
PY - 2023
DO - 10.1587/transfun.2022DMP0008
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
AB - The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms.
ER -