Average case and smoothed competitive analysis of the multi-level feedback algorithm
Average case and smoothed competitive analysis of the multi-level feedback algorithm
复制标题
DOI：
10.1109/sfcs.2003.1238219
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
L. Becchetti;S. Leonardi;A. Marchetti-Spaccamela;G. Schäfer;T. Vredeveld
中科院分区：
文献类型：
--
作者：
L. Becchetti;S. Leonardi;A. Marchetti-Spaccamela;G. Schäfer;T. Vredeveld
在本文中，我们介绍了在线算法的平滑竞争分析的概念。Spielman和Teng（2001）提出了平滑分析，以解释算法的行为，这些算法在实践中运行良好，但从最坏情况分析的角度来看，性能非常差。我们应用这个概念来分析多级反馈（MLF）算法，以最小化总的流动时间的一系列的工作释放随着时间的推移时，一个工作的处理时间只知道在完成时。初始处理时间是[1，2/sup K/]范围内的整数。我们使用部分位随机化模型，其中通过在相当一般的概率分布类别下改变k个最低有效位来平滑初始处理时间。我们证明了MLF的平滑竞争比为O（（2/sup k/spl sigma/）/sup 3/ +（2/sup k/spl sigma/）/sup 2/2/sup K-k/），其中/spl sigma/表示分布的标准差.特别地，当/spl σ/ = /spl θ/（2/sup k/）时，我们得到了O（2/sup K-k/）的竞争比.我们还证明了一个/spl欧米茄/（2/sup K-k/）下界的任何确定性算法，是根据部分位随机化模型平滑处理时间上运行。对于各种其他平滑模型，我们给出了更高的下限/spl Ω/（2/sup K/）。我们的结果的一个直接结果也是MLF的第一个平均情况分析。我们显示了一个恒定的期望比率的总流动时间的MLF的最佳分布下，包括均匀分布。
In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng (2001) to explain the behavior of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1,2/sup K/] We use a partial bit randomization model, where the initial processing times are smoothened by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2/sup k///spl sigma/)/sup 3/ + (2/sup k///spl sigma/)/sup 2/2/sup K-k/), where /spl sigma/ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2/sup K-k/) if /spl sigma/ = /spl Theta/(2/sup k/). We also prove an /spl Omega/(2/sup K-k/) lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, we give a higher lower bound of /spl Omega/(2/sup K/). A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.