Approximating MAX SAT by moderately exponential and parameterized algorithms
From MaRDI portal
Publication:477187
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
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