# Methods for proving upper bound on a-approximiation algorithms? [closed]

I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance.

For example, there's a simple randomized algorithm for the MAX-E3SAT problem, where there are $m$ clauses each consisting of three distinct 3 variables in $\{x_1, ..., x_n \}$.

There's a theorem that if there exists an algorithm which is $(\frac{7}{8} + \epsilon)$-approximation, then $P = NP$.

What method can and should I use for proving such theorems? Could you please provide an example?

More over, regarding the MAX-E3SAT problem, what method can and should I use to prove such claim:

For any instance of MAX-E3SAT the optimum is at least $\frac{7m}{8}$ ? I'm not looking for the proof of this claim, just the method for proving it.

Thanks a lot

• This is really a bunch of questions rolled into one. Please read up on the matter, and ask the three or four questions implied above separately (if you still are in doubt, that is). Jan 13, 2016 at 16:20

You mention two results giving tight bounds on the approximability of MAX-E3SAT: an upper bound (algorithm) and a lower bound (hardness). The upper bound is much simpler than the lower bound in this case. Indeed, using basic probability you can show that a random assignment satisfies $7/8$ of the clauses in expectation, which gives an approximation algorithm whose approximation ratio is at least $7/8$ in expectation. If you don't like randomized algorithms, this algorithm can be derandomized using the method of conditional expectations.
• If you mean that any MAX-E3SAT instance is $7/8$-satisfiable, then a random assignment proves that. Jan 13, 2016 at 21:22