Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with MAX-3SAT:
TR02-070 | 13th December 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.

more >>>

TR03-049 | 25th June 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness of Short Symmetric Instances of MAX-3SAT

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 >>>

ISSN 1433-8092 | Imprint