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
Revision #1 Authors: Wenceslas Fernandez de la Vega, Marek Karpinski
Accepted on: 10th January 2003 00:00
Downloads: 409
Keywords:
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: 417
Keywords:
Abstract:
We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.