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
Prestasi algoritma dalam talian untuk masalah pembungkusan tong sampah biasanya diukur dengan nisbah penghampiran asimptotik. Walau bagaimanapun, walaupun algoritma dalam talian diterangkan secara eksplisit, secara amnya sukar untuk mendapatkan nilai tepat nisbah penghampiran asimptotik. Dalam makalah ini kami menunjukkan teorem yang memberikan nilai tepat nisbah penghampiran asimptotik dalam bentuk tertutup apabila saiz item dan algoritma dalam talian memenuhi beberapa syarat. Selain itu, kami menunjukkan bahawa teorem kami berfungsi sebagai alat yang berkuasa untuk reka bentuk algoritma dalam talian digabungkan dengan pengoptimuman matematik.
Hiroshi FUJIWARA
Shinshu University
Yuta WANIKAWA
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.
Salinan
Hiroshi FUJIWARA, Yuta WANIKAWA, Hiroaki YAMAMOTO, "Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 3, pp. 362-369, March 2021, doi: 10.1587/transinf.2020FCP0004.
Abstract: The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020FCP0004/_p
Salinan
@ARTICLE{e104-d_3_362,
author={Hiroshi FUJIWARA, Yuta WANIKAWA, Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms},
year={2021},
volume={E104-D},
number={3},
pages={362-369},
abstract={The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.},
keywords={},
doi={10.1587/transinf.2020FCP0004},
ISSN={1745-1361},
month={March},}
Salinan
TY - JOUR
TI - Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 362
EP - 369
AU - Hiroshi FUJIWARA
AU - Yuta WANIKAWA
AU - Hiroaki YAMAMOTO
PY - 2021
DO - 10.1587/transinf.2020FCP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2021
AB - The performance of online algorithms for the bin packing problem is usually measured by the asymptotic approximation ratio. However, even if an online algorithm is explicitly described, it is in general difficult to obtain the exact value of the asymptotic approximation ratio. In this paper we show a theorem that gives the exact value of the asymptotic approximation ratio in a closed form when the item sizes and the online algorithm satisfy some conditions. Moreover, we demonstrate that our theorem serves as a powerful tool for the design of online algorithms combined with mathematical optimization.
ER -