ECCC-Report TR03-049https://eccc.weizmann.ac.il/report/2003/049Comments and Revisions published for TR03-049en-usWed, 25 Jun 2003 16:53:34 +0300
Paper TR03-049
| Approximation Hardness of Short Symmetric Instances of MAX-3SAT |
Piotr Berman,
Marek Karpinski,
Alexander D. Scott
https://eccc.weizmann.ac.il/report/2003/049We 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.
Wed, 25 Jun 2003 16:53:34 +0300https://eccc.weizmann.ac.il/report/2003/049