# 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). – vonbrand Jan 13 '16 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. – Yuval Filmus Jan 13 '16 at 21:22