Approximating MAX SAT by moderately exponential and parameterized algorithms
From MaRDI portal
Publication:477187
DOI10.1016/J.TCS.2014.10.039zbMATH Open1303.68155OpenAlexW2174811417MaRDI QIDQ477187FDOQ477187
Authors: Vangelis Th. Paschos, Emeric Tourniaire, 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
Recommendations
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- On Some Recent Approximation Algorithms for MAX SAT
- scientific article; zbMATH DE number 1258327
- scientific article; zbMATH DE number 1302170
- scientific article; zbMATH DE number 1552232
- MAX SAT approximation beyond the limits of polynomial-time approximation
- scientific article; zbMATH DE number 1002206
- Approximation algorithms for the maximum satisfiability problem
- On the Approximation of Maximum Satisfiability
Cites Work
- Which problems have strongly exponential complexity?
- Parameterized Approximation Problems
- Title not available (Why is that?)
- Set partitioning via inclusion-exclusion
- Title not available (Why is that?)
- Approximation and Online Algorithms
- Title not available (Why is that?)
- Exact and approximate bandwidth
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Worst-case study of local search for MAX-\(k\)-SAT.
- An exponential time 2-approximation algorithm for bandwidth
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- A survey on the structure of approximation classes
- Improved exact algorithms for MAX-SAT
Cited In (10)
- Sums of squares based approximation algorithms for MAX-SAT
- MAX SAT approximation beyond the limits of polynomial-time approximation
- In)approximability of Maximum Minimal FVS
- On Some Recent Approximation Algorithms for MAX SAT
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- (In)approximability of maximum minimal FVS
- When polynomial approximation meets exact computation
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- When polynomial approximation meets exact computation
- Moderately exponential time and fixed parameter approximation algorithms
This page was built for publication: Approximating MAX SAT by moderately exponential and parameterized algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477187)
