CNF Greedy Approximation
We consider monotone 3-CNF formulas (exactly three non-negated literals per clause). Goal: set as few variables to TRUE as possible while satisfying all clauses. Greedy-CNF repeatedly picks any remaining clause, sets one variable in it to TRUE, and removes all clauses containing that variable.
What is the approximation ratio of this algorithm?
Correct option: Indeed, the approximation could be as bad as $n - 2$. Consider the instance $(x,y,z_1), (x,y,z_2), \ldots, (x,y,z_k),$ where the $z$s are all distinct. The total number of variables here is $n = k+2$. What if greedy never picks $x$ or $y$? On the one hand, the optimal solution is to clearly just set the variable $x$ to true, or the variable $y$ to true. On the other hand, the greedy algorithm may end up picking all the $z$ variables, which is a solution of size $k = n-2$.