Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2003 Copyright 2003 Universität Bonn, Institut für Informatik, Abt. V
8990

June 26, 2003

Approximation Hardness of Short Symmetric Instances of MAX-3SAT
Piotr Berman, Marek Karpinski and Alexander D. Scott
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 10:27:35
 English
Universität Bonn -> Institut für Informatik -> Abteilung V