A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT

Harry Buhrman, Sevag Gharibian, Zeph Landau +3

We present an extremely simple polynomial-space exponential-time $(1-\epsilon )$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…