We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.
We prove approximation hardness of short symmetric instances
of MAX-3SAT in which each literal occurs exactly twice, and
each clause is exactly of size 3. We display also an explicit
approximation lower bound for that problem. The bound two on
the number ...
more >>>
