1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.