Question 20: Consider the following approximation algorithm for the w…

Consider the following approximation algorithm for the weighted vertex cover problem.

1: Solve the relaxed linear program corresponding to the given problem:

$\begin{aligned} &\text{Minimize} \quad && \textstyle\sum_{i=1}^{n} \mathit{weight}(v_i) \cdot x_i \\ &\text{Subject to} \quad && x_i + x_j \geq 1 \quad \text{for all edges } (v_i, v_j) \in E \\ & && 0 \leq x_i \leq 1 \quad \text{for } 1 \leq i \leq n \end{aligned}$

2: $C \leftarrow \{v_i \in V : x_i \geq 1/2\}$

3: return $C$

Based on the above data, answer the given subquestions.