Approximating MAX SAT by moderately exponential algorithms
Bruno Escoffier, Vangélis Th. Paschos, Émeric Tourniaire · 2011
We study approximation of the max sat problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to max sat in order to get approximation ratios arbitrarily close to 1.