首页> 外文会议>International IPCO Integer Programming and Combinatorial Optimization Conference; 20040607-20040611; New York,NY; US >A Multi-exchange Local Search Algorithm for the Capacitated Facility Location Problem
【24h】

A Multi-exchange Local Search Algorithm for the Capacitated Facility Location Problem

机译:容量限制的设施位置问题的多交换局部搜索算法

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

摘要

We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2(2~(1/2)) - ε and 3 + 2(2~(1/2)) + ε for any given constant ε > 0. Previously known best approximation ratio for the CFLP is 7.88, due to Mahdian and Pal (2003), based on the operations proposed by Pal, Tardos and Wexler (2001). Our upper bound 3+2(2~(1/2))+ε also matches the best known ratio, obtained by Chudak and Williamson (1999), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pal et al. and techniques from the area of parallel machine scheduling.
机译:我们提出了一种多交换本地搜索算法,用于近似失能设施位置问题(CFLP),其中引入了一种新的本地改进操作,该操作可能会同时交换多个设施。我们对算法进行了严格的分析,结果表明该算法的性能保证在3 + 2(2〜(1/2))-ε和3 + 2(2〜(1/2))+ε之间给定常数ε>0。基于Pal,Tardos和Wexler(2001)提出的运算,由于Mahdian和Pal(2003),先前已知的CFLP最佳近似比为7.88。对于具有均匀容量的CFLP,我们的上限3 + 2(2〜(1/2))+ε也与Chudak和Williamson(1999)获得的最著名的比率相匹配。为了获得新算法的紧密边界,我们有趣地利用了Pal等人的交换图的概念。并行机器调度领域的技术和技巧。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号