论文标题
重新审视随机订单的最佳合身垃圾箱包装
Best Fit Bin Packing with Random Order Revisited
论文作者
论文摘要
最佳拟合是用于垃圾箱包装问题的众所周知的在线算法，其中必须将一维物品包装成最少数量的单位大小垃圾箱。在一项开创性的工作中，肯尼（Soda）[Soda 1996]引入了（渐近）随机订单比例，作为在线算法的替代性能度量。在这里，对手指定了这些项目，但是到达顺序是随机统一绘制的。 Kenyon的结果分别建立了1.08和1.5的上限和上限，最佳拟合的随机阶比。尽管这种类型的分析模型在在线算法领域变得越来越流行，但在肯尼恩（Kenyon）结果后，尚未取得最佳拟合算法的进展。 我们通过建立改进的1.10的下限来研究最佳拟合的随机阶率，并考虑到长期的差距。对于所有项目大于1/3的情况，我们表明随机订单比率迅速收敛到1.25。在一般情况下，至关重要地确定了最佳拟合的表现，正是如此大的项目的存在。此外，这种情况与完全在线模型中的经典最大信号匹配问题密切相关。作为附带产品，我们表明，最适合在这种情况下满足单调性属性，与一般情况不同。 此外，我们启动了此问题的绝对随机订单比率的研究。与渐近比相反，即使在可以填充少数垃圾箱的情况下，绝对比率也必须保持。我们表明，最佳拟合的绝对随机订单比至少为1.3。对于所有项目大于1/3的情况，我们分别得出21/16和1.2的上限和下限。
Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon's result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1.2, respectively.
