Department of Computer Science
 
Chair V

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