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.


1 Answer 1


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.

  • 4
    $\begingroup$ Isn't 20/19 better than 1.0957 ? $\endgroup$ Commented Aug 19, 2011 at 19:53
  • 1
    $\begingroup$ There is an older version here. $\endgroup$
    – Kaveh
    Commented Aug 19, 2011 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$ Commented Aug 20, 2011 at 0:22
  • 1
    $\begingroup$ @Lior, you can accept Ryan's answer by clicking on the check mark on his answer. $\endgroup$
    – Kaveh
    Commented Aug 21, 2011 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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