• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The online k-server problem with rejection
【24h】

The online k-server problem with rejection

机译：带拒绝的在线K服务器问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this work we investigate the online k-server problem where each request has a penalty and it is allowed to reject the requests. The goal is to minimize the sum of the total distance moved by the servers and the total penalty of the rejected requests. We extend the work function algorithm to this more general model and prove that it is (4k ? 1)-competitive. We also consider the problem for special cases: we prove that the work function algorithm is 5-competitive if k = 2 and (2k + 1)-competitive for any k ≥ 1 if the metric space is the line. In the case of the line we also present the extension of the double-coverage algorithm and prove that it is 3k-competitive. This algorithm has worse competitive ratio than the work function algorithm but it is much faster and memoryless. Moreover we prove that for any metric space containing at least k + 1 points no online algorithm can have smaller competitive ratio than 2k + 1, and this shows that the work function algorithm has the smallest possible competitive ratio in the case of lines and also in the case k = 2.
机译：在这项工作中，我们调查了在线K服务器问题，其中每个请求都会受到处罚，并且可以拒绝该请求。目的是最大程度地减少服务器移动的总距离与拒绝请求的总损失之和。我们将功函数算法扩展到这个更通用的模型，并证明它具有（4k？1）竞争性。我们还考虑了特殊情况下的问题：证明了如果k = 2，则功函数算法是5竞争的;如果度量空间是线，则对于任何k≥1，（2k + 1）竞争。在生产线的情况下，我们还介绍了双覆盖算法的扩展，并证明了它具有3k竞争能力。该算法的竞争比比功函数算法差，但是它更快且没有内存。此外，我们证明，对于任何包含至少k + 1个点的度量空间，在线算法的竞争比都不会小于2k + 1，这表明在线的情况下，以及情况k = 2。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号