ECCC - TR02-070

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-070 | 10th January 2003 00:00

9/8-Approximation Algorithm for Random MAX-3SAT Revision of: TR02-070

Contact

Add Comment

Revision #1 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Accepted on: 10th January 2003 00:00
Downloads: 1984

Keywords:

Approximation Algorithms, Approximation Schemes, Concentration, MAX-3SAT, Random Instances, Value Approximation

Abstract:

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

Paper:

TR02-070 | 13th December 2002 00:00

9/8-Approximation Algorithm for Random MAX-3SAT

TR02-070 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Publication: 13th December 2002 12:25
Downloads: 1900

Keywords:

Approximation Algorithms, Approximation Schemes, Concentration, MAX-3SAT, Random Instances, Value Approximation

Abstract:

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

ISSN 1433-8092 | Imprint