Set Cover -几个不同的版本

Question

我一直在处理一个具有两组顶点L和R以及一个边集E的二部图。我一直在尝试解决两个不同的问题：

1)简单集覆盖问题(即找到L中最小的顶点基数子集，使得该子集的邻域包含所有R)。据我所知，这个问题被称为命中集问题，等同于集合覆盖问题，并且存在一些近似算法。我想知道你会推荐哪种近似算法，我在网上找到了几种不同的算法。

2)我想要解决的第二个问题与上面的类似，但我不想描述R的全部，而是只想描述R的子集T，而不描述R的任何其他元素。此外，允许的操作包括集合并和集合差以及L中元素的邻域的集合交集。因此，我希望找到L中必须包含在这样的描述中的元素的最小数量。抱歉，如果这一点不清楚，我可以进一步解释并回答任何问题。

我真的很感谢任何人的帮助。

Answer 1

对于1，我推荐integer linear programming。有很多求解器；我个人使用过GLPK (免费)和CPLEX (商业)。

对于2，直观地说，我们希望由所选择的集合导出的维恩图具有这样的属性，即没有一个区域同时包含T中的元素和不包含T中的元素(我假设除了集合补集之外，我们还允许公式中的空集)。我们可以将这个问题归结为一个简单的集合覆盖问题，如下所示。要覆盖的新元素是T中的所有x和R-T中的y的两个元素集合{x，y}。每个旧集合S产生一个新的集合{{x, y} | x in S and y in R - S}。