Approximating MAX SAT by moderately exponential and parameterized algorithms
type: Item
instance of: scholarly article
title: Approximating MAX SAT by moderately exponential and parameterized algorithms
zbMATH Open document ID: 1303.68155
author: Vangelis Th. Paschos
author: Emeric Tourniaire
author: Bruno Escoffier
published in: Theoretical Computer Science
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6376182
zbMATH Keywords: maximum satisfiability
zbMATH Keywords: exponential time algorithms
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2014.10.039
OpenAlex ID: W2174811417
cites work: Q4258216
cites work: Approximation and Online Algorithms
cites work: Q4247437
cites work: Set Partitioning via Inclusion-Exclusion
cites work: Approximation of min coloring by moderately exponential algorithms
cites work: Efficient approximation of Min Set Cover by moderately exponential algorithms
cites work: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
cites work: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
cites work: Improved exact algorithms for MAX-SAT
cites work: Exponential-time approximation of weighted set cover
cites work: Exact and approximate bandwidth
cites work: MAX SAT approximation beyond the limits of polynomial-time approximation
cites work: Parameterized Approximation Problems
cites work: A survey on the structure of approximation classes
cites work: An Exponential Time 2-Approximation Algorithm for Bandwidth
cites work: Q4526964
cites work: Worst-case study of local search for MAX-\(k\)-SAT.
cites work: Which problems have strongly exponential complexity?
DOI: 10.1016/J.TCS.2014.10.039
Recommended article: Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
Recommended article: On Some Recent Approximation Algorithms for MAX SAT
Recommended article: Q4229151
Recommended article: Q4247437
Recommended article: Q4524463
Recommended article: MAX SAT approximation beyond the limits of polynomial-time approximation
Recommended article: Q3129924
Recommended article: Approximation algorithms for the maximum satisfiability problem
Recommended article: On the Approximation of Maximum Satisfiability
description: scientific article; zbMATH DE number 6376182