首页> 外文期刊>Algorithmica >LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
【24h】

LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design

机译:批量购买网络设计中基于LP的设施定位近似算法

获取原文
获取原文并翻译 | 示例

摘要

We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from K different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of O(K), and for the connected version, we get the first LP-based bound of O(1).
机译:我们研究了将批量购买网络设计集成到经典(连接)设施位置问题中的问题。在此类问题中,我们需要开放设施,建立路由网络,并将每个客户需求路由到开放设施。此外,可以从K种不同的电缆类型中以离散单位购买边缘的容量,而成本却可以满足规模经济要求。我们将针对单源批量购买问题的Talwar的线性编程框架(IPCO 2002)扩展到这些变体,并证明设施位置和关联设施位置批量购买问题的完整性缺口上限。对于未连接的变量,我们证明了O(K)的完整性缺口边界,对于连接的版本,我们得到了O(1)的第一个基于LP的边界。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号