Approximating MAX SAT by moderately exponential and parameterized algorithms

DOI10.1016/J.TCS.2014.10.039MaRDI QIDQ477187zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsexponential time algorithmsmaximum satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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

• scientific article; zbMATH DE number 1302170 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• A survey on the structure of approximation classes
• An exponential time 2-approximation algorithm for bandwidth
• Approximation and Online Algorithms
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of min coloring by moderately exponential algorithms
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Exact and approximate bandwidth
• Exponential-time approximation of weighted set cover
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Improved exact algorithms for MAX-SAT
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Parameterized Approximation Problems
• Set partitioning via inclusion-exclusion
• Which problems have strongly exponential complexity?
• Worst-case study of local search for MAX-\(k\)-SAT.

Cited in

(10)

• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Moderately exponential time and fixed parameter approximation algorithms
• When polynomial approximation meets exact computation
• (In)approximability of maximum minimal FVS
• In)approximability of Maximum Minimal FVS
• On Some Recent Approximation Algorithms for MAX SAT
• Sums of squares based approximation algorithms for MAX-SAT
• When polynomial approximation meets exact computation
• Approximating MAX SAT by moderately exponential and parameterized 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)