• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms -ESA 2003 >Universal Facility Location
【24h】

Universal Facility Location

机译：通用设施位置

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

摘要

In the Universal Facility Location problem we are given a set of demand points and a set of facilities. The goal is to assign the demands to facilities in such a way that the sum of service and facility costs is minimized. The service cost is proportional to the distance each unit of demand has to travel to its assigned facility, whereas the facility cost of each facility i depends on the amount of demand assigned to that facility and is given by a cost function f_i(·). We present a (7.88 + ε)-approximation algorithm for the Universal Facility Location problem based on local search, under the assumption that the cost functions fi are nondecreasing. The algorithm chooses local improvement steps by solving a knapsack-like subproblem using dynamic programming. This is the first constant-factor approximation algorithm for this problem. Our algorithm also slightly improves the best known approximation ratio for the capacitated facility location problem with non-uniform hard capacities.
机译：在“通用设施位置”问题中，我们得到了一组需求点和一组设施。目的是将需求分配给设施，以使服务和设施成本的总和最小化。服务成本与每个需求单位必须到达其分配的设施的距离成正比，而每个设施的设施成本i取决于分配给该设施的需求量，并由成本函数f_i（·）给出。我们假设成本函数fi不递减，提出了一种基于局部搜索的通用设施选址问题的（7.88 +ε）近似算法。该算法通过使用动态规划求解类似背包的子问题来选择局部改进步骤。这是针对此问题的第一个恒定因子近似算法。我们的算法还针对具有不均匀硬容量的带电容器设施位置问题，略微提高了最著名的近似率。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号