Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
复制标题
使用因子揭示线性规划的 k 集覆盖近似算法分析
DOI：
--
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
C. Kaklamanis
中科院分区：
文献类型：
--
作者：
Stavros Athanassopoulos;I. Caragiannis;C. Kaklamanis
我们提出了新的组合逼近算法的k-集覆盖问题。以前的方法是基于有效地处理小集合扩展贪婪算法。新的算法进一步扩展了这些方法，利用自然的想法，计算大包装的元素成大尺寸的集合。我们的结果改进了以前的最佳逼近界的k-集覆盖问题的所有值的k≥6。所使用的分析技术可能是独立的利益，上界的近似因子是通过界定的目标值的因素揭示线性规划。
We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of k≥6. The analysis technique used could be of independent interest; the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program.