Approximation Algorithm
近似算法针对组合优化问题！
最小顶点覆盖问题
贪心算法：任取一条边，将两个顶点加入V'，并删去其关联的边，直到所有边都被删除。
可以证明这是一个多项式时间的常数比为2的近似算法，紧实例为由k条互不关联的边构成的图。
顶点覆盖的判定问题是NPC的！
最大团问题 & 最大独立集问题
这两个问题目前认为不存在常数近似比的近似算法。
近似算法针对组合优化问题！
贪心算法：任取一条边，将两个顶点加入V'，并删去其关联的边，直到所有边都被删除。
可以证明这是一个多项式时间的常数比为2的近似算法，紧实例为由k条互不关联的边构成的图。
顶点覆盖的判定问题是NPC的！
这两个问题目前认为不存在常数近似比的近似算法。