Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms

Asymptotic Approximation Ratios for Certain Classes of Online Bin Packing Algorithms
复制标题

DOI：
10.1587/transinf.2020fcp0004
复制
发表时间：
2021-03
期刊：
IEICE Trans. Inf. Syst.
影响因子：
--
通讯作者：
H. Fujiwara;Yuta Wanikawa;Hiroaki Yamamoto
H. Fujiwara;Yuta Wanikawa;Hiroaki Yamamoto
中科院分区：
其他
文献类型：
--
作者：
H. Fujiwara;Yuta Wanikawa;Hiroaki Yamamoto

文献摘要

相似文献

摘要装箱问题的在线算法的性能通常由渐近逼近比来衡量。然而，即使一个在线算法被明确地描述，它是在一般困难，以获得渐近逼近比的精确值。在本文中，我们证明了一个定理，给出了一个封闭形式的渐近逼近比的精确值时，项目大小和在线算法满足一定的条件。此外，我们证明，我们的定理作为一个强大的工具，设计在线算法结合数学优化
SUMMARY 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 di ffi cult 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