Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-049 | 25th June 2003 00:00

Approximation Hardness of Short Symmetric Instances of MAX-3SAT

RSS-Feed

Abstract:

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 of occurrences of literals in symmetric MAX-3SAT
is thus the smallest possible one which makes the instances
hard to approximate.



ISSN 1433-8092 | Imprint