Rheinische Friedrich-Wilhelms-Universität Bonn 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
8987

23.04.2003

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Piotr Berman, Marek Karpinski and Alex D. Scott
[Download PostScript] [Download PDF]

We study approximation hardness and satisfiability of bounded occurrence uniform instances of SAT. Among other things, we prove the inapproximability for SAT instances in which every clause has exactly 3 literals and each variable occurs exactly 4 times, and display an explicit approximation lower bound for this problem. We also provide a tighter characterization of the uniformly bounded occurrence instances which are surely satisfiable.

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

Powered by Zope