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
8985

07.02.2003

1.0957-Approximation Algorithm for Random MAX-3SAT
W. Fernandez de la Vega and Marek Karpinski
[Download PostScript] [Download PDF]

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

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