MAX-SAT 2-Approximation algorithm

Question

I have the two following questions:

1. I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation algorithms)

2. I have this simple randomized algorithm for approximating the MAX-SAT problem:

The algorithm sets each variable to be True independently with probability 1/2 and False with probability 1/2. It then outputs the resulting assignment.

for(i=1,2,...,n){
    set xi = 0 or xi = 1 with probability 1/2 for each case
}

So everywhere I have looked I found people presenting this as an 1/2 approximation algorithm but I'm supposed to prove that this is a 2 approximation algorithm. Can anyone help clarify this?

Answer 1

A $1/2$-approximation algorithm and a $2$-approximation algorithm are exactly the same thing.

Here are two definitions of a $\rho$-approximation algorithm for a maximization problem:

1. On an instance whose optimal value is $O$, the algorithm is guaranteed to output a solution whose values is at least $\rho \cdot O$.
2. On an instance whose optimal value is $O$, the algorithm is guaranteed to output a solution whose values is at least $O/\rho$.

The first definition only makes sense when $\rho \leq 1$, while the second only makes sense when $\rho \geq 1$. Some people prefer the first one, others prefer the second one. Fortunately, you can tell from the value of $\rho$ which one is meant (when $\rho = 1$, both concepts are the same).