• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems
【24h】

A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems

机译：约束因子显示LP的系统方法及其在度量和平方度量设施位置问题中的应用

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

摘要

A systematic technique to bound factor-revealing linear programs is presented. We show how to derive a family of upper bound factor-revealing programs (UPFRP), and that each such program can be solved by a computer to bound the approximation factor. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the Metric Facility Location Problem (MFLP) and to a generalization where the distance function is a squared metric. We call this generalization the Squared Metric Facility Location Problem (SMFLP) and prove that there is no approximation factor better than 2.04, assuming P ≠ NP. Then, we analyze the best known algorithms for the MFLP based on primal-dual and LP-rounding techniques when they are applied to the SMFLP. We prove very tight bounds for these algorithms, and show that the LP-rounding algorithm achieves a ratio of 2.04, and therefore has the best factor for the SMFLP. We use UPFRPs in the dual-fitting analysis of the primal-dual algorithms for both the SMFLP and the MFLP, improving some of the previous analysis for the MFLP.
机译：提出了一种约束因子揭示线性程序的系统技术。我们展示了如何导出一系列上限因子揭示程序（UPFRP），并且每个这样的程序都可以由计算机求解以限制近似因子。获得UPFRP很简单，可以用作分析证明的替代方法，这些证明通常很长且很繁琐。我们将此技术应用于度量标准设施位置问题（MFLP）以及距离函数为平方度量标准的概括。我们称这种推广为平方度量衡设备位置问题（SMFLP），并证明在假定P≠NP的​​情况下，没有比2.04更好的逼近因子。然后，在将原始对偶和LP舍入技术应用于SMFLP时，我们分析了最著名的MFLP算法。我们证明了这些算法的严格界限，并表明LP舍入算法的比率为2.04，因此具有SMFLP的最佳系数。我们在SMFLP和MFLP的原始对偶算法的双重拟合分析中使用了UPFRP，从而改进了MFLP的先前分析。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号