The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
复制标题
DOI：
10.1137/120885309
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
René Sitters
中科院分区：
文献类型：
--
作者：
René Sitters
广义的2服务器问题是一个在线优化问题，必须以最低的成本提供一系列请求。请求一个一个接一个地到达，需要立即由两台服务器中的至少一台服务。我们考虑了两个服务器的成本函数可能不同的一般模型。正式地，每个服务器都在自己的度量空间中移动，并且请求由每个度量空间中的一个点组成。通过将两个服务器之一移至其请求点，可以使用它。必须在不了解未来请求的情况下提出请求。目的是最大程度地减少总距离。两种服务器在实际线路上移动的特殊情况称为CNN问题。我们表明，通用的工作功能算法，$ \ mathrm {wfa} _ {\ lambda} $，对于广义的2服务器问题而言一直是竞争力的。此外，我们为$ k \ geqslant2 $服务器提供了概述，并讨论了我们的技术和工作功能算法的适用性。我们合并...
The generalized 2-server problem is an online optimization problem where a sequence of requests has to be served at minimal cost. Requests arrive one by one and need to be served instantly by at least one of two servers. We consider the general model where the cost function of the two servers may be different. Formally, each server moves in its own metric space and a request consists of one point in each metric space. It is served by moving one of the two servers to its request point. Requests have to be served without knowledge of future requests. The objective is to minimize the total traveled distance. The special case where both servers move on the real line is known as the CNN problem. We show that the generalized work function algorithm, $\mathrm{WFA}_{\lambda}$, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to $k\geqslant2$ servers and discuss the applicability of our techniques and of the work function algorithm in general. We co...