設置封面 - 幾個不同的版本

Question

我一直在處理與兩組頂點L和R，邊集E的二部圖。我一直試圖解決幾個不同的問題：

1）簡單集覆蓋問題（即找到L中頂點的最小基數子集，使得該子集的鄰域包含全部R）。據我所知，這個問題被稱爲命中集問題，相當於集覆蓋問題和一些近似算法存在。我想知道你會推薦什麼近似算法，我在網上找到了幾個不同的近似算法。

2）我想要解決的第二個問題與上面類似，但是我不想描述所有的R，而只想描述T，R的一個子集，沒有任何其他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}。