Approximating MAX SAT by moderately exponential and parameterized algorithms

DOI10.1016/j.tcs.2014.10.039zbMath1303.68155MaRDI QIDQ477187

Emeric Tourniaire, Vangelis Th. Paschos, Bruno Escoffier

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.039

zbMATH Keywords

approximation algorithms; maximum satisfiability; exponential time algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W25: Approximation algorithms

Related Items

When polynomial approximation meets exact computation, When polynomial approximation meets exact computation, In)approximability of Maximum Minimal FVS, (In)approximability of maximum minimal FVS, Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• A survey on the structure of approximation classes
• Exact and approximate bandwidth
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Worst-case study of local search for MAX-\(k\)-SAT.
• Which problems have strongly exponential complexity?
• Improved exact algorithms for MAX-SAT
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Parameterized Approximation Problems
• Set Partitioning via Inclusion-Exclusion
• An Exponential Time 2-Approximation Algorithm for Bandwidth
• Approximation and Online Algorithms
• MAX SAT approximation beyond the limits of polynomial-time approximation