Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2002 Copyright 2002 University of Bonn, Department of Computer Science, Abt. V
85245

13.12.2002

9/8-Approximation Algorithm for Random MAX-3SAT
W. Fernandez de la Vega, Marek Karpinski
[Download PostScript] [Download PDF]

We prove that MAX-3SAT can be approximated in polynomial time within a factor 9/8 on random instances.

Last Change: 11/05/14 at 10:23:57
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V