<p>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:</p>

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

<p>Her result has apparently been improved further by <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=8224129">Fernandez de la Vega and Karpinski</a> to 1.0957, but I cannot find an online preprint of this paper.</p>

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

CC BY-SA 3.0
2011-08-19T19:53:02.233Z
Isn't 20/19 better than 1.0957 ?
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-19T21:40:33.867Z
There is an older version [here](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2003/85247-CS.ps.gz).
Kaveh
CC BY-SA 3.0
2011-08-20T00:22:07.227Z
Ha, thanks! I mistakenly assumed that since one result was published after the other one, clearly the latter bound must be better...
Ryan Williams
CC BY-SA 3.0
2011-08-21T05:57:18.787Z
@Lior, you can accept Ryan's answer by clicking on the check mark on his answer.
Kaveh
CC BY-SA 3.0
2011-08-19T19:16:35.407Z
2011-08-19T19:16:35.407Z
Ryan Williams
<p>It is known [<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.3836" rel="noreferrer">de la Vega &amp; Karpinski 2002</a>] 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-18T13:27:13.320Z
What do you mean by "approximate 3-SAT"?  Do you mean "approximate MAX-3-SAT"?
Tyson Williams
CC BY-SA 3.0
2011-08-18T13:32:40.150Z
“[Fernandez et. al]” is a very poor way of citing a paper.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-18T13:44:15.570Z
@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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.3836), which also confirms my previous comment (that we are talking about MAX-3-SAT, not 3-SAT).
Tyson Williams
<ds.algorithms><sat><approximation-hardness><pcp><random-k-sat>
Approximating Random MAX-k-SAT
Lior Eldar
# Approximating Random MAX-k-SAT

(Asked by: username_0 on 2011-08-18)

It is known [[de la Vega & Karpinski 2002](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.3836)] 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.

**Tags:** ds.algorithms, sat, approximation-hardness, pcp, random-k-sat
> **Comments:**
> **username_1**: What do you mean by "approximate 3-SAT"?  Do you mean "approximate MAX-3-SAT"?  
> **username_2**: “[Fernandez et. al]” is a very poor way of citing a paper.  
> **username_1**: @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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.3836), which also confirms my previous comment (that we are talking about MAX-3-SAT, not 3-SAT).  

---

## 1 answers

### Answer by username_3 on 2011-08-19. Score: 9 | Accepted answer

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](http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8224129) 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.

> **Comments:**
> **username_4**: Isn't 20/19 better than 1.0957 ?  
> **username_5**: There is an older version [here](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2003/85247-CS.ps.gz).  
> **username_3**: Ha, thanks! I mistakenly assumed that since one result was published after the other one, clearly the latter bound must be better...  
> **username_5**: @Lior, you can accept Ryan's answer by clicking on the check mark on his answer.  

---

