Methods for proving upper bound on a-approximiation algorithms? [closed]
-
03-11-2019 - |
Frage
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
Keine korrekte Lösung