• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem; Probability rept
【24h】

Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem; Probability rept

机译：度量无容量设施选址问题的最优Bifactor逼近算法;概率来看

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The authors consider the metric uncapacitated facility location problem (UFL). In the paper the authors 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. The linear programming rounding algorithm is the first one that touches the approximability limit curve established by Jain et al. As a consequence, they obtain the first optimal approximation algorithm for instances dominated by connection costs. The new algorithm - when combined with a (1.11,1.7764)-approximation 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. Additionally, the authors show that a single randomized clustering procedure could be used instead of the greedy clustering used in the algorithms of Shmoys et al., Chudak et al., Sviridenko, and in the current paper.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号