2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – vonbrand Jan 13 '16 at 16:20
2
$\begingroup$

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.

The other direction is much harder, and relies on the PCP theorem and Raz's parallel repetition theorem. It was shown by Håstad in his seminal paper Some optimal inapproximability results. This is all described in Arora and Barak's textbook, but I warn you that the textbook is quite advanced.

$\endgroup$
  • $\begingroup$ I read a little bit about the PCP theorem in The Design of Approximation Algorithms book, but did not understand all of it. The exercise I'm dealing with expects I prove the later claim in my post with a simpler method. I was wondering if you could think of another simpler way for proving it. Thanks $\endgroup$ – johni Jan 13 '16 at 21:15
  • 1
    $\begingroup$ If you mean that any MAX-E3SAT instance is $7/8$-satisfiable, then a random assignment proves that. $\endgroup$ – Yuval Filmus Jan 13 '16 at 21:22
  • $\begingroup$ What do you mean by "random assignment"? do you mean that showing an algorithm that on average produces an assignment that will satisfy 7/8 of the clauses is sufficient? Thanks $\endgroup$ – johni Jan 13 '16 at 21:24
  • $\begingroup$ Read the first paragraph of my answer again. All the answers are there. At this point, I suggest you spend a few hours trying to solve this on your own, using these hints. $\endgroup$ – Yuval Filmus Jan 13 '16 at 21:25

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