algorithm - Set Cover 的非贪心算法

Question

关于我的集合的详细信息：每个集合正好有M个元素，每个元素正好属于N个集合。

我需要一个非贪心算法来计算最小集覆盖的大小。

有没有好的算法？（对于我的特殊情况）

谢谢。

Answer 1

硬度结果和可能的不可近似性结果（可能具有更差的常数）甚至适用于您的特殊情况。对混合整数程序使用求解器，例如GLPK。