A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
For researchers in approximation algorithms for MAX-k-SAT, this provides a simpler and slightly faster algorithm, though the improvement is incremental.
The paper presents a simpler polynomial-space exponential-time (1-ε)-approximation algorithm for MAX-k-SAT that is slightly faster than previous algorithms by Hirsch and Escoffier et al. The algorithm repeatedly samples random assignments until finding one satisfying a large enough fraction of clauses, and its efficiency is proven by showing that many assignments satisfy a fraction close to the optimal.
We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value.