20211220-Set Cover Problem

发表于 更新于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

Weighted Set Cover (WSC)：带权集合覆盖问题

Set Cover Problem

研究这个问题，是因为看到论文中提及了Weighted Set Cover (WSC)，并论证该问题是NP-hard的。因此我希望了解什么是Weighted Set Cover。为了说明这个问题，我们首先需要知道集合覆盖(Set Cover)和顶点覆盖(Vertex Cover)的区别。

1. 集合覆盖(Set Cover)和顶点覆盖(Vertex Cover)

1.1 Set Cover
  • 定义
  • 有包含了m个元素的集合A（注意，集合是无序的，并且包含的元素也是不相同的）。现有n个集合，分别为${B_1,B_2,…,B_n}$，这n个集合的并集恰好等于A集合，即: $A=B_{1} \cup B_{2} \cup B_{3} \cup \ldots \cup B_{n}$。
    • 问题：是否存在B集合的最小子集，且他们的并集也等于A集合？
    • 举例：集合$A=\{1,2,3,4,5\}$，集合$B=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$。可以看出，B集合的并集恰好等于A集合，那么问题的解是$SETCOVER=\{\{1,2,3\},\{4,5\}\}$。
1.2 Vertex Cover

  • 定义

    有图G=(V, E)，是否存在V的子集V’，使得|V’|<=|V|，并且G中的每条边e，至少有一个顶点在$|V^{‘}|$中？

  • 这个问题有一个NPO（No Optimization Problem）的变种，即：找到满足条件的最小顶点集，也就是使得满足条件下最小值$|V^{‘}|$。

1.3 二者比较
  • 这是两类完全不同的问题，set cover属于集合一类问题，应用于计算机科学以及计算理论方面。vertex cover，属于图论一类问题，应用于计算机科学、计算理论、图论、数学等等方面。

2. 集合覆盖(Set Cover)的解决方案

现在我们希望对集合覆盖问题的解决方案进行说明。

思想：首先遍历一遍单个子集，看看有无覆盖的。没有则再组合两个子集看有无全覆盖的。没有再组合三个子集……

特点：暴力但简单

思想：循环直到不满足条件 输出子集个数。

1
2
3
4
5
6
7
8
9
for si in S:
    S-si == u
    delete si
    break

for ki in S-si:
    if S-si-ki == U:
    delete  ki
    break

特点：不一定是全局最优的，但是可以满足大部分情况

2.3 数学转化 math formulation

思路：将问题转成一个integer liner problem，然后再松弛成liner problem 进行求解。

1

2

3. 参考

  • GeeksforGeeks
  • Set Cover Problem | Set 1 (Greedy Approximate Algorithm)
  • Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)
  • Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree)