The minimum 3-CNF problem is the problem of finding the minimum number of literals $x_i$ of a formula $F$ to set true such that $F$ evaluates to true. In this problem all literals are positive. Now the question is how to find a 3-approximation algorithm for the minimum 3-CNF problem and prove it is a 3-approximation algorithm?
Hint: Use an algorithm similar to the approximate vertex cover algorithm.
We generate a graph $G = (V, E)$ with each clause in $F$ a vertex $v \in V$ and each edge $(v_i, v_j)$ in $E$ if literal $x_k$ is in both clauses $v_i, v_j$. We add an edge from a vertex to itself if a clause shares no literals with other clauses. Now, $F$ evaluates to true if each edge in $G$ is covered. An optimal solution to the problem sets the minimum number of literals to be true. This corresponds with the smallest set $R \subset V$ which covers all $(u,v) \in E$. This is the standard vertex-cover problem.
We have the following algorithm APPROX-VERTEX-COVER-MOD$(G)$:
APPROX-VERTEX-COVER-MOD$(G)$
$\quad$ $C = \emptyset$
$\quad$ $E' = G.E$
$\quad$ $\textbf{while}$ $E' \neq \emptyset$:
$\qquad$ Let $(u,v)$ be an arbitrary edge of $E'$.
$\qquad$ $C = C \cup x_j \in \{u\}$
$\qquad$ Remove all edges incident on $u$ and $v$ from $E'$.
$\quad$ $\textbf{return}$ $C$
Now, the algorithm selects an edge, stores the literals of one of the vertices of the edge in $C$ then deletes all edges incident on $u$ and $v$. Let $A$ be the set of edges selected by the algorithm and $C^*$ the optimal vertex cover. The algorithm computes a vertex cover of $G$ so each edge in $E$ is covered. It selects edges which share no endpoints which means at least one literal of a selected edge must be true and so $|A| \leq |C^*|$. The algorithm selects three literals for each selected edge, so $|C| = 3|A| \leq 3 |C^*|$. The algorithm is therefore a 3-approximation algorithm.
