Better algorithms for unfair metrical task systems and applications
Better algorithms for unfair metrical task systems and applications
复制标题
针对不公平度量任务系统和应用程序的更好算法
DOI：
10.1145/335305.335408
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
M. Mendel
中科院分区：
文献类型：
--
作者：
A. Fiat;M. Mendel
不公平任务测量系统是在线任务测量系统的一种推广。在本文中，我们引入了一些新的技术来结合不公平度量任务系统的算法，并应用这些技术来获得任意度量空间上度量任务系统的改进的随机在线算法。1. 介绍。由Borodin、Linial和Saks（11）提出的度量任务系统（metric task system, mts）可以描述如下：处于某种内部状态的服务器接收具有与每种内部状态相关的服务成本的任务。服务器可以切换状态，支付由状态空间上定义的度量空间给出的成本，然后支付与新状态相关的服务成本。mts一直是大量研究的主题。对在线算法的大部分研究可以看作是对某些特定的MTS的研究。在将其中一些问题建模为MTS时，允许的任务集被限制为适合问题的细节。在本文中，我们考虑mts的原始定义，其中任务集可以是任意的。竞争比为2n−1的任意n态MTS的确定性算法
Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces. 1. Introduction. Metrical task systems (MTSs), introduced by Borodin, Linial, and Saks (11), can be described as follows: A server in some internal state receives tasks that have a service cost associated with each of the internal states. The server may switch states, paying a cost given by a metric space defined on the state space, and then pays the service cost associated with the new state. MTSs have been the subject of a great deal of study. A large part of the research into online algorithms can be viewed as a study of some particular MTS. In modelling some of these problems as MTSs, the set of permissible tasks is constrained to fit the particulars of the problem. In this paper we consider the original definition of MTSs, where the set of tasks can be arbitrary. A deterministic algorithm for any n-state MTS with a competitive ratio of 2n − 1