# 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

## closed as too broad by vonbrand, Evil, David Richerby, Luke Mathieson, JuhoJan 16 '16 at 18:08

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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