這一講會展示將問題轉化為線性規劃的 form (但可能是 ILP)，利用 LP solver 得到解，做 LP relaxation 並證明這個解不會太差 (approx. ratio 不太大)。
Vertex Cover Problem
Given a graph $G$, a vertex cover is a set of vertices $S$
s.t. $\forall (u,v) \in E, \; \text{either} \, u \in S \, \text{or} \, v \in S$
Want: Find the vertex cover $S$ with $\min$ # of nodes
Formulation
For each $v_i \in V$, assign a variable $x_i = $𝟙[$v_i$ is chosen]
$x_i \in \mathbb{Z}$ 這個條件，讓問題是困難的 ILP (which is NPC) ，在此我們把拿掉 (LP relaxation)，轉成 LP 。
2-Approx Algorithm
Run 過 LP solver 後，可得到一組滿足限制式的解 $\mathbf{x}^{\star}$
但這並不是原問題的答案，我們需要利用它找出滿足條件的 $\mathbf{x}^{\prime}$，
有個簡單的演算法
Correctness
$\because x_i + x_j \geq 1$，$x_i, x_j$ 中至少有一個 $\geq \frac{1}{2}$，所以每條邊至少會有一個端點被選
Approx. Ratio
Worst Case 就是所有 $x_i = \frac{1}{2}$，那麼便會每條邊的兩個端點都會被選起來。
推廣
可以視為 Set Cover Problem with every element is covered by $\leq l$ 個 subset 的特例 ($l = 2$)，
由此也可推知Set Cover Problem 的 $l$-approx algorithm。