【24h】

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

机译:度量无能力设施定位问题的最佳双因子逼近算法

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

摘要

We consider the metric uncapacitated facility location prob-lem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)-approximation algorithm for the UFL problem. Our linear programing rounding algorithm is the first one that touches the approximability limit curve (γf, 1 + 2e ~(-γf)) established by Jain et al. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. Our new algorithm - when combined with a (1.11,1.7764)-approxima-tion algorithm proposed by Jain, Mahdian and Saberi, and later analyzed by Mahdian, Ye and Zhang - gives a 1.5-approximation algorithm for the metric UFL problem. This algorithm improves over the previously best known 1.52-approximation algorithm by Mahdian, Ye and Zhang, and it cuts the gap with the approximability lower bound by 1/3. The algorithm is also used to improve the approximation ratio for the 3-level version of the problem.
机译:我们考虑度量能力丧失能力的位置问题(UFL)。在本文中,我们修改了Chudak和Shmoys的(1 + 2 / e)逼近算法,以获得一种针对UFL问题的新的(1.6774,1.3738)逼近算法。我们的线性规划舍入算法是第一个接触Jain等人建立的近似极限曲线(γf,1 + 2e〜(-γf))的算法。结果,对于连接成本占优势的实例,我们获得了第一个最佳逼近算法。我们的新算法-与Jain,Mahdian和Saberi提出的(1.11,1.7764)近似算法结合使用,然后由Mahdian,Ye和Zhang分析后,给出了度量UFL问题的1.5近似算法。该算法比Mahdian,Ye和Zhang先前最著名的1.52逼近算法有所改进,并且以1/3的逼近度下界缩小了差距。该算法还用于提高问题的3级版本的近似率。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号