Albers Susanne, Khan Arindam, Ladewig Leon
Department of Computer Science, Technial University of Munich, Boltzmannstr. 3, 85748 Garching, Germany.
Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 560012 India.
Algorithmica. 2021;83(9):2833-2858. doi: 10.1007/s00453-021-00844-5. Epub 2021 Jul 1.
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) 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 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.
最佳适配是一种针对装箱问题的著名在线算法，在该问题中，一维物品的集合必须被装入最少数量的单位尺寸箱子中。在一项开创性工作中，凯尼恩（Kenyon，[SODA 1996]）引入了（渐近）随机顺序比作为在线算法的一种替代性能度量。在此，对手指定物品，但到达顺序是从所有可能顺序中均匀随机抽取的。凯尼恩的结果分别为最佳适配的随机顺序比确定了1.08和1.5的下界和上界。尽管这种分析模型在在线算法领域越来越受欢迎，但自凯尼恩得出结果后，最佳适配算法一直没有取得进展。我们研究最佳适配的随机顺序比，并通过建立1.10的改进下界来缩小长期存在的差距。对于所有物品都大于1/3的情况，我们表明随机顺序比迅速收敛到1.25。正是这种大尺寸物品的存在在一般情况下决定性地决定了最佳适配的性能。此外，这种情况与完全在线模型中的经典最大基数匹配问题密切相关。作为一个附带成果，我们表明最佳适配在这类实例上满足单调性属性，这与一般情况不同。另外，我们开启了对该问题绝对随机顺序比的研究。与渐近比不同，绝对比即使对于可以装入少量箱子的实例也必须成立。我们表明最佳适配的绝对随机顺序比至少为1.3。对于所有物品都大于1/3的情况，我们分别推导出了21/16和1.2的上界和下界。
