• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms and Computation; Lecture Notes in Computer Science; 4288 >Improved Approximation for Single-Sink Buy-at-Bulk
【24h】

Improved Approximation for Single-Sink Buy-at-Bulk

机译：改进的单槽批量购买的近似值

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

摘要

In the single-sink buy-at-bulk network design problem we are given a subset of source nodes in a weighted undirected graph: each source node wishes to send a given amount of flow to a sink node. Moreover, a set of cable types is given, each characterized by a cost per unit length and by a capacity: the ratio cost/capacity decreases from small to large cables by economies of scale. The problem is to install cables on edges at minimum cost, such that the flow from each source to the sink can be routed simultaneously. The approximation ratio of this NP-hard problem was gradually reduced from O(log~2 n) to 65.49 by a long series of papers. In this paper, we design a better 24.92 approximation algorithm for this problem.
机译：在单接收器批量购买网络设计问题中，我们在加权无向图中获得了源节点的子集：每个源节点都希望向接收器节点发送给定的流量。此外，给出了一组电缆类型，每种电缆的特征是单位长度的成本和容量：成本/容量的比率因规模经济而从小电缆到大电缆减小。问题在于以最小的成本将电缆安装在边缘上，以便可以同时路由从每个水源到水槽的水流。一连串的论文将此NP-hard问题的近似率从O（log〜2 n）逐渐减小到65.49。在本文中，我们针对此问题设计了一种更好的24.92近似算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号