集合覆盖的不贪心算法

Question

我的套装详细信息:每个集合恰好有M个元素，每个元素恰好属于N个集合。

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

有好的算法吗?(对于我的特殊情况)

谢谢。

Answer 1

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