ad12.pdf

看优化问题和判定问题的转换

A ≤ p* OPT, 证明即为不知道OPT的情况下

Vertex Cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set {\displaystyle S} of vertices such that for every two vertices in {\displaystyle S}, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in {\displaystyle S}.

|M| ≤ OPT , 因为M是选取没有共享顶点的边， OPT是最小的顶点覆盖的的边的个数 ？？？可是和最小比诶?

A 算法是把两端都选中了，A = 2|M| ≤ 2OPT

近似比：2

优化的三个方向

1. Can the approximation guarantee of Algorithm be improved by a better analysis?
   1. 这个近似算法里面的近似比还可以再小吗
2. Can an approximation algorithm with a better guarantee be designed using the lower bounding scheme of Algorithm?
   1. 这个优化算法还可以再改进吗？
3. Is there some other lower bounding method that can lead to an improved approximation guarantee for Vertex cover?
   1. 有没有别的更好的优化算法？

Can the Guarantee be Improved?

说明2是一个tight bound