We address the problem of constructing randomized online algorithms for the Metrical Task Systems (MTS) problem on a metric 5 against an oblivious adversary. Restricting our attention to the class of "work-based" algorithms, we provide a framework for designing algorithms that uses the technique of regularization. For the case when S is a uniform metric, we exhibit two algorithms that arise from this framework, and we prove a bound on the competitive ratio of each. We show that the second of these algorithms is In n + O(log log n) competitive, which is the current state-of-the art for the uniform MTS problem.
展开▼
机译：我们解决了针对公制对手在度量标准5上构建度量任务系统（MTS）问题的随机在线算法的问题。为了限制我们对“基于工作”算法的关注，我们提供了使用正则化技术设计算法的框架。对于S是统一度量的情况，我们展示了两种从该框架产生的算法，并且证明了每种算法的竞争率都有界。我们表明，这些算法中的第二种具有In n + O（log log n）竞争性，这是统一MTS问题的最新技术。
展开▼
