# Approximating Random MAX-k-SAT

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.

• What do you mean by "approximate 3-SAT"? Do you mean "approximate MAX-3-SAT"? Aug 18 '11 at 13:27
• “[Fernandez et. al]” is a very poor way of citing a paper. Aug 18 '11 at 13:32
• @Tsuyoshi Ito I think the full citation is 9/8-Approximation Algorithm for Random MAX-3SAT (2002) by W. Fernandez de la Vega, Marek Karpinski, which also confirms my previous comment (that we are talking about MAX-3-SAT, not 3-SAT). Aug 18 '11 at 13:44

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.

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