• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Distributed Computing and Networking >Finding Facilities Fast
【24h】

Finding Facilities Fast

机译：快速查找设施

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

摘要

Clustering can play a critical role in increasing the performance and lifetime of wireless networks. The facility location problem is a general abstraction of the clustering problem and this paper presents the first constant-factor approximation algorithm for the facility location problem on unit disk graphs (UDGs), a commonly used model for wireless networks. In this version of the problem, connection costs are not metric, i.e., they do not satisfy the triangle inequality, because connecting to a non-neighbor costs ∞. In non-metric settings the best approximation algorithms guarantee an O(log n)-factor approximation, but we are able to use structural properties of UDGs to obtain a constant-factor approximation. Our approach combines ideas from the primal-dual algorithm for facility location due to Jain and Vazirani (JACM, 2001) with recent results on the weighted minimum dominating set problem for UDGs (Huang et al, J. Comb. Opt, 2008). We then show that the facility location problem on UDGs is inherently local and one can solve local subproblems independently and combine the solutions in a simple way to obtain a good solution to the overall problem. This leads to a distributed version of our algorithm in the LOCAL model that runs in constant rounds and still yields a constant-factor approximation. Even if the UDG is specified without geometry, we are able to combine recent results on maximal independent sets and clique partitioning of UDGs, to obtain an O(log n)-approximation that runs in O(log~* n) rounds.
机译：群集在提高无线网络的性能和寿命方面可以发挥关键作用。设施位置问题是聚类问题的一般抽象，本文提出了单位盘图（UDG）上设施位置问题的第一个常数因子近似算法，这是无线网络常用的模型。在此问题的版本中，连接成本不是度量标准的，即它们不满足三角形不等式，因为连接到非邻居成本∞。在非度量设置中，最佳近似算法可以保证O（log n）因子近似，但是我们能够使用UDG的结构特性来获得恒定因子近似。我们的方法结合了Jain和Vazirani（JACM，2001）提出的用于设施定位的原始对偶算法的思想，以及有关UDG的加权最小支配集问题的最新结果（Huang等，J。Comb。Opt，2008）。然后，我们证明UDG上的设施位置问题本质上是本地的，并且可以独立解决本地子问题，并以简单的方式组合解决方案以获得对整体问题的良好解决方案。这导致本机算法在本地模型中的分布式版本，该版本以恒定回合方式运行，并且仍产生恒定因子近似值。即使指定的UDG没有几何图形，我们也可以将关于最大独立集的最新结果和UDG的派系划分相结合，以获得以O（log〜* n）轮次运行的O（log n）逼近。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号