|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2003 | Copyright 2003 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |