• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >New and Improved Bounds for the Minimum Set Cover Problem
【24h】

New and Improved Bounds for the Minimum Set Cover Problem

机译：最小集覆盖问题的新边界和改进边界

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

摘要

We study the relationship between the approximation factor for the Set-Cover problem and the parameters Δ : the maximum cardinality of any subset, and k : the maximum number of subsets containing any element of the ground set. We show an LP rounding based approximation of (k - 1)(1 - e~(-in Δ/k-1)) + 1, which is substantially better than the classical algorithms in the range k ≈ ln Δ, and also improves on related previous works [19,22]. For the interesting case when k = θ(log Δ) we also exhibit an integrality gap which essentially matches our approximation algorithm. We also prove a hardness of approximation factor of Ω (log Δ/(log log Δ)~2 ) when k = θ(log Δ). This is the first study of the hardness factor specifically for this range of k and Δ, and improves on the only other such result implicitly proved in [18].
机译：我们研究了Set-Cover问题的近似因子与参数Δ之间的关系：Δ：任何子集的最大基数，k：包含地面集合的任何元素的子集的最大数目。我们展示了基于LP舍入的（k-1）（1- e〜（-inΔ/ k-1））+ 1的近似值，它在k≈lnΔ范围内明显优于经典算法，并且还提高了关于以前的相关作品[19,22]。对于有趣的情况，当k =θ（logΔ）时，我们还表现出了一个与我们的近似算法基本匹配的完整性缺口。当k =θ（logΔ）时，我们还证明了近似系数Ω的硬度（logΔ/（log logΔ）〜2）。这是专门针对k和Δ范围的硬度因子的首次研究，并且对[18]中隐含证明的唯一其他此类结果进行了改进。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号