Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study
Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study
复制标题
离散分布和连续分布下的平均案例分析之间的根本差异：装箱案例研究
DOI：
10.1145/103418.103446
复制
发表时间：
1991
期刊：
影响因子：
3.7
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
E. Coffman;C. Courcoubetis;M. Garey;David S. Johnson;L. McGeoch;P. Shor;R. Weber;M. Yannakakis
本文考虑一维箱分组算法的平均情况，其中箱具有单位容量，项目大小根据“离散均匀”分布U~（k），1 s j < k选择，其中集合{11 k，21 k，.，k）具有被选择的概率1/j。注意，对于固定的j，k，分布U{？nj;在U（O，jlk]中，项目大小在半开区间（O，jik]内均匀选取。在本文中，我们表明，平均情况下的行为可以有很大的不同，在两种类型的分布。我们证明了对于所有的j，k，j < k-1，存在在U~; k]下具有常数期望浪费的在线算法，而对于任何u s 1，在U（O，U]下没有在线算法可以具有小于C2（n1 '2）的浪费.相应地，尽管对于所有u < 1/2，首次拟合递减（离线）算法在U（0，u]下具有恒定的预期浪费，但是存在许多组合j，k，其中j < k/2，使得首次拟合递减在U（j;k）下具有t3（t1）预期浪费。对于j = 6和k = 13，比例常数被最大化，在这种情况下，预期的浪费k为nl 624。
We consider the average case behavior of onedmensional bin paekmg algorithms in the case where bins have unit capacity and item sizes are chosen according to the ‘ ‘dficrete uniform” distribution U~; k), 1 s j < k, where each item size in the set {llk,21k,..., ji k) has probability 1/j of beiig chosen. Note that for fixed j,k the distributions U{?nj;mk]’ approach the continuous distribution U(O, jlk] as m A W, where in U(O, jl k] the item sizes are chosen uniformly horn the half-open interval (O,jik]. In this paper, we show that average case behavior can differ substantially under the two types of distributions. We show that for all j, k, j < k-1, there exist on-line algorithms that have constant expected waste under U~; k], whereas no on-line algorithm can have less than C2(n1’2) waste under U(O, U] for any u s 1. Conmariwise, although the First Fit Decreasing (off-line) algorithm has constant expected waste under U(O, u] for all u < 1/2, there are many combinations j,k with j < k/2 such that First Fit Decreasing has t3(tI) expected waste under U(j;k). The constant of proportionality is maxtilzed for j = 6 and k = 13, in which case the expected waste k nl 624.