It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.

Should one expect this to be close to optimal? In fact, is it possible, that random MAX-k-SAT instances can be approximated within any desirable fraction w.h.p.? At least on the face of it - this should not contradict the PCP theorem, whose output SAT instances are very construction-specific (Dinur) and are thus sets with negligible probability in this respect.


Their result is not optimal. First, it was improved upon by Yannet Interian. She obtained a 20/19 approximation (if I recall correctly). See the reference:

Y. Interian. Approximation algorithm for Random MAX-kSAT. Theory and Applications of Satisfiability Testing (SAT 2004), Revised Selected Papers. LNCS 3542, 2005.

Her result has apparently been improved further by Fernandez de la Vega and Karpinski to 1.0957, but I cannot find an online preprint of this paper.

Given such a low approximation ratio, I wonder if it is reasonable to conjecture that there is a PTAS.

| cite | improve this answer | |
  • 4
    $\begingroup$ Isn't 20/19 better than 1.0957 ? $\endgroup$ – Mahdi Cheraghchi Aug 19 '11 at 19:53
  • 1
    $\begingroup$ There is an older version here. $\endgroup$ – Kaveh Aug 19 '11 at 21:40
  • $\begingroup$ Ha, thanks! I mistakenly assumed that since one result was published after the other one, clearly the latter bound must be better... $\endgroup$ – Ryan Williams Aug 20 '11 at 0:22
  • 1
    $\begingroup$ @Lior, you can accept Ryan's answer by clicking on the check mark on his answer. $\endgroup$ – Kaveh Aug 21 '11 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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