• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >New Approximation Results for Resource Replication Problems
【24h】

New Approximation Results for Resource Replication Problems

机译：资源复制问题的新的近似结果

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

摘要

We consider several variants of a basic resource replication problem in this paper, and propose new approximation results for them. These problems are of fundamental interest in the areas of P2P networks, sensor networks and ad hoc networks, where optimal placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several k-center type problems, yields simple and efficient approximation algorithms for resource replication problems. Our results range from positive (efficient, small constant factor, approximation algorithms) to extremely negative (impossibility of existence of any algorithm with non-trivial approximation guarantee, i.e., with positive approximation ratio) for different versions of the problem.
机译：我们在本文中考虑了基本资源复制问题的几种变体，并为它们提出了新的近似结果。这些问题在P2P网络，传感器网络和ad hoc网络领域具有根本的意义，在这些领域中，副本的最佳放置是性能的主要瓶颈。我们观察到阈值图技术已应用于多个k中心类型的问题，它为资源复制问题提供了简单有效的近似算法。对于不同版本的问题，我们的结果从正值（有效，小常数因子，近似算法）到极度负数（不可能存在具有非平凡近似保证的算法，即具有正近似率的算法）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号