Advertisement
Published in:
2012 | OriginalPaper | Chapter
Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
Authors : Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
Published in: Theory and Applications of Models of Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.