• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Prize-Collecting Survivable Network Design in Node-Weighted Graphs
【24h】

Prize-Collecting Survivable Network Design in Node-Weighted Graphs

机译：节点加权图中的奖品收集生存网络设计

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

摘要

We consider node-weighted network design problems, in particular the survivable network design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a node-weighted undirected graph G = (V, E) and integral connectivity requirements r(st) for each pair of nodes st. The goal is to find a minimum node-weighted subgraph H of G such that, for each pair st, H contains r(st) edge-disjoint paths between s and t. PC-SNDP is a generalization in which the input also includes a penalty π(st) for each pair, and the goal is to find a subgraph H to minimize the sum of the weight of H and the sum of the penalties for all pairs whose connectivity requirements are not fully satisfied by H. Let k = max_(st) r(st) be the maximum requirement. There has been no non-trivial approximation for node-weighted PC-SNDP for k > 1, the main reason being the lack of an LP relaxation based approach for node-weighted SNDP. In this paper we describe multiroute-fiow based relaxations for the two problems and obtain approximation algorithms for PC-SNDP through them. The approximation ratios we obtain for PC-SNDP are similar to those that were previously known for SNDP via combinatorial algorithms. Specifically, we obtain an O(k~2 log n)-approximation in general graphs and an O(k~2)-approximation in graphs that exclude a fixed minor. The approximation-ratios can be improved by a factor of k but the running times of the algorithms depend polynomially on n~k.
机译：我们考虑节点加权网络设计问题，特别是可生存网络设计问题（SNDP）及其奖品收集版本（PC-SNDP）。输入由节点加权无向图G =（V，E）和每对节点st的积分连通性要求r（st）组成。目的是找到G的最小节点加权子图H，以便对于每对st，H包含s和t之间的r（st）个边缘不相交的路径。 PC-SNDP是一种概括，其中输入还包括每对对的惩罚π（st），目标是找到一个子图H，以使H的权重之和和所有对的惩罚对的总和最小。 H不能完全满足连接性要求。令k = max_（st）r（st）为最大要求。对于k≥1的节点加权PC-SNDP，没有不平凡的近似，主要原因是缺乏针对节点加权SNDP的基于LP松弛的方法。在本文中，我们针对这两个问题描述了基于多路径流的松弛，并通过它们获得了PC-SNDP的近似算法。我们针对PC-SNDP所获得的近似比率与之前通过组合算法对SNDP所知的近似比率相似。具体来说，我们在一般图中获得O（k〜2 log n）逼近，而在排除固定小调的图中获得O（k〜2）n逼近。近似比率可以提高k倍，但是算法的运行时间在多项式上取决于n〜k。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号