...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Approximating Minimum-Power Degree and Connectivity Problems
【24h】

Approximating Minimum-Power Degree and Connectivity Problems

机译：近似最小功率度和连接性问题

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

摘要

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph G = (V, ε) with edge costs {c(e) :e∈ε} and degree requirements {r(v): v ∈ V}, the Minimum-Power Edge-Multi-Cover (MPEMC) problem is to find a minimum-power subgraph G of G so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC, improving the previous ratio O(log~4 n). This is used to derive an O(logn + α)-approximation algorithm for the undirected Minimum-Power k-Connected Subgraph (MPkCS) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, α =O(log k • log n-k) which is O(logi k) unless k = n - o(n), and is O(log~2 k) = O(log~2 n) for k =n - o(n). Our result shows that the min-power and the min-cost versions of the k-Connected Subgraph problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.
机译：功率优化是无线网络设计中的核心问题。给定一个在边上具有成本的图，则节点的幂是入射到其上的边的最大代价，而图的幂是其节点的幂之和。受无线网络中应用程序的推动，我们在功耗最小化标准下考虑了一些基本的无向网络设计问题。给定一个图G =（V，ε）且边成本为{c（e）：e∈ε}，度数为{r（v）：v∈V}，则最小功率边多覆盖（MPEMC）问题是找到G的最小功率子图G，以使G中每个节点v的度数至少为r（v）。我们给出了MPEMC的O（log n）近似算法，提高了以前的比率O（log〜4 n）。它用于导出无向最小功率k连通子图（MPkCS）问题的O（logn +α）近似算法，其中α是该问题的最小成本变量的最佳已知比率。当前，α= O（log k•log n / nk），除非k = n-o（n），否则为O（logi k），对于k，为O（log〜2 k）= O（log〜2 n） = n-o（n）。我们的结果表明，k-Connected子图问题的最小功效和最小成本版本在近似值方面是等效的，除非最小成本变量允许o（log n）近似值，这似乎不存在此刻到达。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号