Displaying similar documents to “Product replacement in the Monster.”

1.0957-Approximation Algorithm for Random MAX-3SAT

Wenceslas Fernandez de la Vega, Marek Karpinski (2007)

RAIRO - Operations Research

Similarity:

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