Unfair Problems and Randomized Algorithms for Metrical Task Systems
Unfair Problems and Randomized Algorithms for Metrical Task Systems
复制标题
度量任务系统的不公平问题和随机算法
DOI：
--
复制
发表时间：
1999
影响因子：
1
通讯作者：
S. Seiden
中科院分区：
文献类型：
--
作者：
S. Seiden
Borodin，Linial和Saks提出了一种称为度量任务系统的在线系统通用模型(1992，J.Assoc.电脑。机器39(4)，745？763)。本文研究了不公平两状态问题，它是两状态度量任务系统问题的自然推广。给出了该问题的一个随机化算法，结果表明该算法是最优的。利用对不公平两态问题的分析，证明了一个类似于Blum，Karloff，Rabani和Saks(1992)的分解定理。介绍了第33届计算机科学基础研讨会，“197？207页”。这个定理允许人们为特定的测量任务系统设计分而治之的算法。我们的定理给出了渐近相同的界，但它具有较少的限制边界条件。
Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992,J. Assoc. Comput. Mach.39(4), 745?763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science,” pp. 197?207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.