Approximation Algorithms (1)

Approximation Ratios

• The cost $C$ of the solution produced by the algorithm is within a factor of $\rho(n)$ of the cost $C^*$ of an optimal solution

• $max(\displaystyle{{C^*}\over{C}},\displaystyle{{C}\over{C^*}}) \leq \rho(n)$

• For maximization problem, $1\leq \displaystyle{{C^*}\over{C}} \leq \rho(n)$

• For minimization problem, $1\leq \displaystyle{{C}\over{C^*}} \leq \rho(n)$

• If an algorithm achieves an approximation ratio of $\rho(n)$, call it $\rho(n)$-approximation algorithm

• 1-approximation algorithm = optimal solution

• A large approximation ratio may return a solution that is much worse than optimal

Approximation Scheme

• An approximation scheme for an optimization problem is an approximation algorithm
• Takes as input not only an instance of the problem, but also $\epsilon > 0$
• such that for any fixed $\epsilon$, the scheme is an $(1+\epsilon)$-approximation algorithm

Polynomial-time approximation scheme

• Running time can increase very rapidly as $\epsilon$ decreases
• e.g.) a scheme with $O(n^{2/\epsilon})$ time
• If $\epsilon$ decreases by a constant factor,
  the running time to achieve the desired approximation should not increase by more than a constant factor

Fully polynomial-time approximation scheme

• Running time is polynomial both in $1/\epsilon$ and in the size $n$ of the input instance
• Any constant factor decrease in $\epsilon$ comes with a constant factor increase in the running time
• e.g.) a scheme with $O((1/\epsilon)^2n^3)$ time

---

Vertex Cover Problem

• Though we can't find the optimal solution in polynomial time,
  we can effectively find a vertex cover that is near-optimal
• A vertex cover size is guaranteed to be no more than twice the size of an optimal vertex cover
• Running time is $O(|V|+|E|)$
  
• Example
  
  
• Approximated solution is $\{b,c,e,f,d,g\}$
• Optimal solution is $\{b,d,e\}$

Approximation algorithm is a polynomial-time 2-approximation algorithm

• 모든 edge 는 선택되거나 제거되기 때문에 모든 edge 는 한 번씩만 봄
• The set $C$ is a vertex cover, since the algorithm loops until every edge in $G.E$ has been covered by some vertex in $C$
• Let $A$ represent the set of edges that are included in $C$
• An optimal vertex cover $C^*$ must include at least one endpoint of each edge that is included in $C$
• $|C^*| \geq |A|$
  • $C^*$ 는 $A$ 를 모두 커버해야하기 때문에 $A$ 의 edge 중 하나의 vertex 는 무조건 가짐
• Each iteration picks an edge for which neither endpoint is in $C$,
  $|C|=2|A|$ and $|C| \leq 2|C^*|$
  • $A$ 는 항상 이전에 보지 못한 vertex 들의 edge 를 선택하기 때문에 개수는 $C$ 의 절반

---