• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Approximating the k-splittable capacitated network design problem
【24h】

Approximating the k-splittable capacitated network design problem

机译：逼近k可分裂的电容网络设计问题

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

摘要

We consider the k-Splittable Capacitated Network Design Problem (kSCND) in a graph G = (V, E) with edge weight w(e) >= 0, e E E. We are given a vertex t E V designated as a sink, a cable capacity lambda > 0, and a source set S subset of V with demand d(v) >= 0, v E S. For any edge e E E, we are allowed to install an integer number x(e) of copies of e. The kSCND asks to simultaneously send demand d(v) from each source v E S along at most k paths to the sink t. A set of such paths can pass through an edge in G as long as the total demand along the paths does not exceed the capacity x(e)lambda. The objective is to find a set P of paths of G that minimize the installing cost Sigma(e is an element of E) x(e)w(e).In this paper, we propose a ((k + 1)/k + P-ST)-approximation algorithm to the kSCND, where P-ST is any approximation ratio achievable for the Steiner tree problem. (C) 2016 Elsevier B.V. All rights reserved.
机译：我们在图G =（V，E）且边权重w（e）> = 0，e E E的图中考虑k可分裂电容网络设计问题（kSCND）。给定一个顶点t EV，指定为汇点，电缆容量lambda> 0，并且V的源集S子集的需求d（v）> = 0，v ES。对于任何边e EE，我们都可以安装整数x（e）的副本e。 kSCND要求同时沿着最多k条路径将每个源v E S的需求d（v）同时发送到宿t。只要沿着这些路径的总需求不超过容量x（e）lambda，一组这样的路径就可以通过G中的一条边。目的是找到一组G的路径P，以使安装成本最小化Sigma（e是E的元素）x（e）w（e）。在本文中，我们提出（（k + 1）/ k kSCND的近似算法），其中P-ST是Steiner树问题可达到的任何近似比率。 （C）2016 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号