# 近似基础

1. 顶点覆盖问题
   - 给定一个无向图 $G=(V,E)$，求一个顶点子集 $V'\subseteq V$，使得 $E$ 中每条边的至少一个顶点位于 $V'$ 中，且 $V'$ 的大小最小
   - 这是一个 NP-hard 问题，但是可以用近似算法求解
   - 随机选一条边，然后将这条边两个顶点都加入到 $V'$ 中，去除所有这两个顶点相关的边，重复这个过程直到所有边都被去除
   - 这是一个 2-近似算法，因为可能只需要一个顶点就可以覆盖一条边，但选取的会是两个顶点，$|V'|=2|A|,|V^*|\geqslant|A|$

2. 集合覆盖问题
   - 给定一个集合 $U$，以及 $U$ 的一个子集合族 $S$，求一个子集合族 $S'\subseteq S$，使得 $S'$ 中的所有子集合的并集等于 $U$，且 $|S'|$ 最小
   - 这也是一个 NP-hard 问题，但是可以用近似算法求解
   - 每次选取一个子集，使得其包含的未去除元素最多，然后将这个子集加入到 $S'$ 中，去除所有这个子集包含的元素，重复这个过程直到所有元素都被去除
   - 这是一个 $H_n$-近似算法，其中 $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$，$|S'|\leqslant H_n|S^*|+1$，即 $\log n$ 近似比

