论文标题
随机在线垃圾箱包装的近乎最佳算法
Near-optimal Algorithms for Stochastic Online Bin Packing
论文作者
论文摘要
我们在两个随机设置下研究在线垃圾箱问题。在垃圾箱包装问题中，为我们提供了n个大小（0,1）的项目，目的是将它们包装到最小数量的单位尺寸垃圾箱中。首先，我们研究了I.I.D.模型下的bin包装，在I.I.D.模型中，独立采样材料大小是独立采样的，在该材料中，在（0,1中的分布）中，它们的分布和一个项目都不知道。而且，在1个尺寸的垃圾箱中，我们提供了一个简单的元估计值，它采用了$α$α$ - 抗肌的近似算法，并提供多项式$（α+ \ varepsilon）$ - 使用IS.I.D的在线bin nline， bin包装，我们提供了一个线性时间$（1+ \ varepsilon）$ - 在i.i.d下的在线bin包装的竞争算法，从而解决了问题。 然后，我们研究了随机阶模型，其中一个对手指定项目，但是项目到达顺序是从所有项目排列的集合中均匀地绘制的。 Kenyon的开创性结果[SODA'96]表明，最佳拟合算法在随机级模型中最多具有3/2的竞争比率，并且猜想的比率约为1.15。但是，即使在特殊情况下，打破3/2的障碍是一个长期的开放问题。最近，Albers等。在特殊情况下，当所有项目量大于1/3时，在特殊情况下显示出对5/4竞争比的改善。对于这种特殊情况，我们通过表明最佳拟合的比率为1来解决分析。我们通过打破3/2的3/2障碍而进一步取得了进一步的进步，这是一个众所周知的bin包装的困难特殊情况，其中所有项目尺寸都在（1/4,4,1/2）中。
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the minimum number of unit-sized bins. First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one and their sizes are revealed upon their arrival and they must be packed immediately and irrevocably in bins of size 1. We provide a simple meta-algorithm that takes an offline $α$-asymptotic approximation algorithm and provides a polynomial-time $(α+ \varepsilon)$-competitive algorithm for online bin packing under the i.i.d. model, where $\varepsilon$>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time $(1+\varepsilon)$-competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary specifies the items, but the order of arrival of items is drawn uniformly at random from the set of all permutations of the items. Kenyon's seminal result [SODA'96] showed that the Best-Fit algorithm has a competitive ratio of at most 3/2 in the random-order model, and conjectured the ratio to be around 1.15. However, it has been a long-standing open problem to break the barrier of 3/2 even for special cases. Recently, Albers et al. [Algorithmica'21] showed an improvement to 5/4 competitive ratio in the special case when all the item sizes are greater than 1/3. For this special case, we settle the analysis by showing that Best-Fit has a competitive ratio of 1. We make further progress by breaking the barrier of 3/2 for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in (1/4,1/2].
